INTERNATIONAL GONGRESS

378 -11Q333 -11 305 15T277 90Q277 108 280 121T283 145Q283 167 269 183T234 206T200 217T182 220H180Q168 178 159 139T145 81T136 44T129 20T122 7T111 -2Q98 -11 83 -11Q66 -11 57 -1T48 16Q48 26 85 176T158 471L195 616Q196 629 188 632T149 637H144Q134 637 131 637T124 640T121 647Z"> (n, k, L)

. Using these ideas, we can get the following.

Proposition 4.4. Let

n = 1, 2, 3, \dots

. The following are equivalent over

{R C A}_{0}

$m {G P H}_{k}^{n} (k = 2, 3, 4, \dots, m = 1, 2, 3, \dots)$ .
${G P H}_{2}^{n}$ on $N$ : for any largeness notion $L$ , there exists a finite set $F \subseteq N$ such that $F$ is 1 -dense $(n, 2, L)$ .

To give a characterization of GPH, we consider the following variants of the infinite Ramsey theorem which was originally introduced by Flood [11].

Definition 4.5 (Ramsey-type weak KÃ´nig's lemma). An infinite homogeneous function for an infinite

(n, k)

-coloring tree

T

X_{0}

is a function

h : [X]^{n} \to k

such that

X \subseteq X_{0}

is infinite and for any

m \in N

, there exists

p \in T

such that

h ↾ [X \cap m]^{n} = p ↾ [X \cap m]^{n}

We define two forms of the Ramsey-type weak KÃ³nig's lemma,

{R W K L}_{k}^{n}

and

{R W K L}_{k}^{n -}

, as follows:

${R W K L}_{k}^{n -}$ : for any infinite $(n, k)$ -coloring tree $T$ on $N$ , there exists an infinite homogeneous function for $T$ ( $n \geq 1$ and $k \geq 2$ ),
${R W K L}_{\infty}^{n -} \equiv \forall k {R W K L}_{k}^{n -}, {R W K L}_{\infty}^{\infty -} \equiv \forall n {R W K L}_{\infty}^{n -}$ ,
${R W K L}_{k}^{n}$ : for any infinite $(n, k)$ -coloring tree $T$ on $N$ , there exists a constant infinite homogeneous function for $T$ ( $n \geq 1$ and $k \geq 2$ ),
${R W K L}_{\infty}^{n} \equiv \forall k {R W K L}_{k}^{n}, {R W K L}_{\infty}^{\infty} \equiv \forall n {R W K L}_{\infty}^{n}$ .

Note that the original definition of Ramsey-type weak KÅ‘nig's lemma by Flood is our RWKL

_{2}^{1}

^{7}

Over RCA

_{0}

, it is strictly in-between WKL and DNR (see [11,12]). Variants of Ramsey-type weak KÃ³nig's lemma with homogeneous functions are introduced and studied by Bienvenu, Patey, and Shafer in [2] and the definition of

{R W K L}_{k}^{n -}

is inspired by them.

Theorem 4.5. Let

n \geq 1

n = \infty

and

k \geq 2

k = \infty

. The following are equivalent over

{R C A}_{0}

${G P H}_{k}^{n}$ .
${FIRT}_{k}^{n}$ .
RWKL $_{k}^{n}$ .
${R T}_{k}^{n} + {R W K L}_{k}^{n -}$ .

Proof. It is enough to show the equivalence for the case

n \geq 1

and

k \geq 2

. Equivalence

3 \leftrightarrow 4

is easy from the definition. If

f : [N]^{< N} \to N

is asymptotically stable, then

L = {F : \exists G \subseteq

7 The original name in [11] was "Ramsey-type KÃ³nig's lemma", but "Ramsey-type weak KÃ³nig's lemma" turned to be the standard name in the later works.

F | G | > f (G)}

is a largeness notion, which implies

1 \to 2

. Conversely, if

L

is a largeness notion, then a function

f

defined as

f (F) = min {| G | - 1 : G \subseteq F \land G \in L} \cup {| F |}

is asymptotically stable and

F \in L \leftrightarrow | F | > f (F)

. This implies

2 \to 1

. Implication

3 \to 1

is a standard compactness argument which we have seen in Proposition 3.1. To show

1 \to 3

, let

T

be an infinite

(n, k)

-coloring tree on

N

with no infinite constant homogeneous function. Define

L

F \in L

if there is no

p \in T

such that

p

is constant on

[F]^{n}

. Then, one can check that

L

is a largeness notion, and hence by 1 , there exists a finite set

F_{0} \subseteq N

which is 1 -dense

(n, k, L)

. Take some

p \in T

so that

dom (p) \supseteq {[F_{0}]}^{n}

, then there must exist

H \subseteq F_{0}

such that

H \in L

and

p

is constant on

[H]^{n}

, which is a contradiction.

In case

n = 3, 4, 5, \dots

, any of the statements in the above theorem is just equivalent to

{A C A}_{0}

, so we mostly interested in the case

n = 1

and 2 . On the other hand, unlike

{R T}_{2}^{1}

{P H}_{2}^{1}

, the principle

{G P H}_{2}^{1}

is still not trivial since

{R W K L}_{2}^{1}

(which is equivalent to

{R W K L}_{2}^{1 -}

) is not provable within

{R C A}_{0}

. This may be interpreted as saying that the generalized version of the Paris-Harrington principle cannot be proved without using some compactness argument. In general,

{R W K L}_{k}^{n -}

is easily implied by

{W K L}_{0}

, but we do not know whether it is strictly weaker than WKL over

{R C A}_{0}

or not in case

n \geq 2

4.3. Iterations of generalized $P H$ and correctness statements

The iterated version of GPH can be related to stronger correctness statements.

Theorem 4.6. Let

k = 2

k = \infty

. Then

{I t G P H}_{k}^{2}

is equivalent to

r Π_{2}^{1}

-corr

({W K L}_{0} + {R T}_{k}^{2})

over

{W K L}_{0}

Over

{A C A}_{0}^{'}

, any

Π_{2}^{1}

-formula (of possibly nonstandard length) is equivalent to a

r Π_{2}^{1}

-formula, and thus

r Π_{2}^{1}

-truth predicate is actually the truth predicate for all

Π_{2}^{1}

-formulas. Furthermore, It is known that

r Π_{2}^{1} - corr ({A C A}_{0})

is equivalent to

{A C A}_{0}^{'} .^{8}

So we simply write

Π_{2}^{1} - corr (T)

for

r Π_{2}^{1} - corr (T)

T \supseteq {A C A}_{0}

Theorem 4.7. The following are equivalent over

{R C A}_{0}

RT.
GPH.
${ItGPH}_{k}^{n} (n = 3, 4, \dots, k = 2, 3, \dots, \infty)$ .
$Π_{2}^{1} - corr ({A C A}_{0})$ .

Theorem 4.8. Over

{R C A}_{0}

, ItGPH is equivalent to

Π_{2}^{1}

corr ({A C A}_{0}^{'})

We will see the proofs of these theorems using indicators in the next section.

The strength of

{I t G P H}_{2}^{2}

{I t G P H}^{2}

is rather unclear. It is not difficult to check that

{R C A}_{0} + {I t G P H}_{2}^{2}

implies

{R T}^{2}

and

{W K L}_{0} + {R T}_{2}^{2} + I Σ_{1}^{1}

implies ItGPH

^{2}

as in the proof of Proposition 3.1. (Note that even ItGPH does not imply

∣ Σ_{1}^{1}

since

I Σ_{1}^{1}

is never implied from
any true

Π_{2}^{1}

-statement.) In particular, they are true in any

ω

-models of

{W K L}_{0} + {R T}_{2}^{2}

. Meanwhile, the following questions are still open.

Question 4.6.

1. Is

{I t G P H}_{2}^{2}

equivalent to

{R T}^{2}

over

{W K L}_{0}

Does ${A C A}_{0}$ imply ItGPH $^{2}$ or ${I t G P H}_{2}^{2}$ ?

5. INDICATORS AND CORRECTNESS STATEMENTS

The notion of indicators is introduced by Kirby and Paris [23,32] to show several independence results from PA, and its theory is organized systematically by Kaye [21]. The argument of indicators can connect first-order objects with second-order objects by means of nonstandard models. Recently, indicators have been used to calibrate the proof-theoretic strength of the infinite Ramsey theorem in the context of reverse mathematics

[6, 24, 34, 46]

5.1. Models of first- and second-order arithmetic

To introduce the argument of indicators, we first set up basic model theory of firstand second-order arithmetic. For the details, see

[16, 21, 26, 39]

. A structure for

L_{1}

is a 6-tuple

M = (M; 0^{M}, 1^{M}, +^{M}, \times^{M}, \leq^{M})

. (We often omit the superscript

M

if it is clear from the context.) An

L_{1}

-structure

ℜ = (ℜ; 0, 1, +, \times, \leq)

where

0, 1, +, \times, \leq

are usual is called the standard model, and an

L_{1}

-structure is said to be nonstandard if it is not isomorphic to

ℜ

. When we consider an expanded language

L_{1} \cup \vec{U}

where

\vec{U} = U_{1}, \dots, U_{k}

are secondorder constants, an

L_{1} \cup \vec{U}

-structure is a pair

(M, {\vec{U}}^{M})

where

M

is an

L_{1}

-structure and

U_{i} \subseteq M

. We may consider

N

as a special second-order constant which satisfies

\forall x x \in N

, in other words,

N^{M} = M

for any

M

. For second-order arithmetic, we use Henkin semantics. A structure for

L_{2}

is a pair

(M, S)

where

M

is an

L_{1}

-structure and

S \subseteq P (M)

. Thus, any

L_{1} \cup \vec{U}

-structure can be considered as an

L_{2}

-structure.

Let

M

be a nonstandard model of EFA

\vec{U}

. We write

[M]^{< M}

for the set of all "finite sets in

M

" (also called

M

-finite sets), in other words,

[M]^{< M} = {([N]^{< N})}^{M}

. A nonempty proper subset

I ⊊ M

is said to be a cut if

a < b \land b \in I

implies

a \in I

for any

a, b \in M

(denoted by

I \subseteq_{e} M

) and

a + 1 \in I

for any

a \in I

. If

I

is a cut and

φ (x)

is a

Σ_{0}^{\vec{U}}

-formula such that

M ⊨ φ (a)

for any

a \in I

(resp.

a \in M ∖ I

), then there exists

a \in M ∖ I

(resp.

a \in I

) such that

M ⊨ φ (a)

. This principle is called overspill (resp. underspill). A cut

I \subseteq_{e} M

is said to be semiregular if for any

F \in [M]^{< M}

with

| F | \leq min F, F \cap I

is bounded in

I

In our study, models of

{W K L}_{0}

play central roles. Here are two important theorems.

Theorem 5.1 (Harrington, see Section IX. 2 of [39]).

For any countable model $(M, S) ⊨ {RCA}_{0}$ , there exists $\bar{S} \supseteq S$ such that $(M, \bar{S}) ⊨$ WKL. $^{9}$
${W K L}_{0}$ is $Π_{1}^{1}$ -conservative over ${R C A}_{0}$ .

9 Model

(M, S)

is said to be countable if both of

M

and

S

are countable.

Theorem 5.2 (see, e.g., Theorems 7.1.5 and 7.1.7 of [26]). Let

M

be a model of EFA and

I ⊊_{e} M

be a cut. Then,

I

is semiregular if and only if

(I, Cod (M / I)) ⊨ {W K L}_{0}

, where

Cod (M / I) = {F \cap I : F \in [M]^{< M}}

5.2. Indicators

Now we give the definition of indicators. Here, we slightly arrange the definition in [21] so as to fit better with second-order arithmetic.

Definition 5.1 (Indicators). Let

\vec{U} = U_{1}, \dots, U_{k}

be second-order constants, and let

T \supseteq

EFA be an

L_{2}

-theory.

Let $M$ be a countable nonstandard model of EFA $\vec{U}$ . A $Σ_{0}^{\vec{U}}$ -definable function $Y : [M]^{< M} \to M$ is said to be an indicator for $T$ on $M$ if for each $F, F^{'} \in [M]^{< M}, Y (F) \leq max F, Y (F) \leq Y (F^{'})$ if $F \subseteq F^{'}$ , and

(cut)

Y (F) > m

for any

m \in N

if and only if there exists a cut

I ⊊ e M

and

S \subseteq Cod (M / I)

such that

(I, S) ⊨ T, U_{i}^{M} \cap I \in S

for each

U_{i} \in \vec{U}

and

F \cap I

is unbounded in

I

A $Σ_{0}^{\vec{U}}$ -formula $Y (F, m)$ is said to be an indicator for $T$ if for any countable nonstandard model $M ⊨ {E F A}^{\vec{V}}$ with $\vec{U} \subseteq \vec{V} (\vec{U}$ is a subtuple of $\vec{V}$ ), $Y$ defines an indicator for $T$ on $M$ .

For a given indicator

Y

, we define two statements "

Y \geq m

" and "

Y

int

\geq m

" as follows:

\begin{aligned} Y \geq m \equiv \forall X_{0} (X_{0} is infinite \to \exists F \subseteq_{fin} X_{0} Y (F) \geq m) \\ Y^{int} \geq m \equiv \forall a \exists b Y ([a, b)_{N}) \geq m \end{aligned}

Note that

Y \geq m

is ar

Π_{1}^{1}

-statement while

Y^{i n t} \geq m

is a

Π_{2}

-statement.

Theorem 5.3. Define

Σ_{0}

-formulas

Y_{{P H}^{n}} (F, m), Y_{P H} (F, m)

, and

Y_{{I t P H}_{k}^{n}} (F, m)

as follows:

$Y_{{P H}^{n}} (F, m) \leftrightarrow m = max {k^{'} \leq max F : F$ is 1-dense $(n, k^{'})} \cup {0} (n = 2, 3, \dots)$ ,
$Y_{P H} (F, m) \leftrightarrow m = max {n^{'} \leq max F : F$ is 1-dense $(n^{'}, 2)} \cup {0}$ ,
$Y_{{I t P H}_{k}^{n}} (F, m) \leftrightarrow m = max {m^{'} \leq max F : F$ is $m^{'}$ -dense $(n, k)} \cup {0} (n = 2, 3, \dots$ or $n = \infty$ and $k = 2, 3, 4, \dots$ or $k = \infty)$ .

Then, we have the following:

$Y_{{P H}^{n}}$ is an indicator for ${R C A}_{0} + 1 Σ_{n - 1}^{0}$ .
$Y_{P H}$ is an indicator for ${A C A}_{0}$ .
$Y_{{I t P H}_{k}^{n}}$ is an indicator for ${W K L}_{0} + {R T}_{k}^{n}$ .

In addition, these facts are provable within

{W K L}_{0}

Proof. For statements 1 and 2, one can reformulate the discussions of [21, SECTIoN 14.3]. Statement 3 is essentially due to Paris [32, EXAMPLE 2] (see also [6, THEOREM 1] and [34, LEMMA 3.2]). We sketch the proof for statement 3 for the case

n = 2, 3, \dots

and

k = 2, 3, \dots

lows from Proposition 3.1 and overspill. For the left-to-right direction, let

M

be a countable nonstandard model of EFA

\vec{U}

and let

F \in [M]^{< M}

m

-dense

(n, k)

for any

m \in ℜ

. By overspill, take

d \in M ∖ ℜ

such that

F

d

-dense

(n, k)

. We will construct a countable decreasing sequence of

M

-finite sets

{F_{i}}_{i \in ℜ}

such that

F_{i}

(d - i)

-dense

(n, k)

and

(i) if

E \in [M]^{< M}

and

| E | \leq E

, then

E \cap {[min F_{i}, max F_{i})}_{N} = \emptyset

for some

i \in ℜ

(ii) if

p \in [M]^{< M}

and

p : [F]^{n} \to k

, then for some

i \in ℜ, F_{i}

p

-homogeneous. Once such a sequence is constructed, put

I = {a \in M : \exists i \in ℜ (a < min F_{i})}

. Then,

F_{i} \cap I

is unbounded in

I

and

U_{i}^{M} \cap I \in Cod (M / I)

. By Theorem 5.2,

(I, Cod (M / I)) ⊨ {W K L}_{0}

since

I

is a semiregular cut by (i), and (ii) implies

(I, Cod (M / I)) ⊨ {R T}_{k}^{n}

Finally, we construct

{F_{i}}_{i \in ℜ}

. Since

[M]^{< M}

is countable, it is enough to show:

(i) if

E \in [M]^{< M}, | E | \leq min E

and

F

ℓ + 1

-dense

(n, k)

then there exists

F^{'} \subseteq F

which is

ℓ

-dense

(n, k)

such that

E \cap {[min F_{i}, max F_{i})}_{N} = \emptyset

(ii)' if

p \in [M]^{< M}, p : [F]^{n} \to k

and

F

ℓ + 1

-dense

(n, k)

with

ℓ \geq 1

, then there exists

F^{'} \subseteq F

which is

ℓ

-dense

(n, k)

such that

F

p

-homogeneous.

Indeed, (ii)' is trivial from the definition of density. For (i)', define

c : [F]^{2} \to 2

c ({x, y}) =

0 \leftrightarrow [x, y)_{N} \cap E = \emptyset

, and take a

c

-homogeneous set

F^{'} \subseteq F

such that

F^{'}

ℓ

-dense

(n, k)

{[F^{'}]}^{2} \subseteq c^{- 1} (1)

, then put

F^{''} = F^{'} ∖ {min F^{'}}

and we have

| F^{''} | \leq | E | \leq min E < min F^{''}

, but

F^{''}

must be relatively large since it is at least 0 -dense

(n, k)

. Hence

{[F^{'}]}^{2} \subseteq c^{- 1} (0)

, which we are done.

For the next theorem, we want to formalize model-theoretic arguments within second-order arithmetic. Within

{W K L}_{0}

, one can set up basic (countable) model theory for first-order logic, and then prove GÃ¶del's completeness theorem [39, SECTIONS II. 8 AND IV.3]. Standard techniques for countable nonstandard models of arithmetic such as the compactness theorem, over/underspill, back and forth, recursive saturation and forcing are naturally formalizable once a countable model with a full evaluation function (truth definition) is provided. On the other hand, it is not possible in general to consider

N

itself as a model of first-order arithmetic since its truth definition is too complicated,

^{10}

hence it is not easy to guarantee that a family of true sentences are consistent. Still, we can deal with the consistency of

Π_{2}

-sentences as follows.

Lemma 5.4.

{R C A}_{0}

proves the following. Let

\vec{A} = A_{1}, \dots, A_{k}

be sets, and let

Γ

be a set of true

Π_{2}^{\vec{A}}

-sentences. Then,

Γ

is consistent (with considering

\vec{A}

as second-order constants).

^{11}

Proof. We work within

{R C A}_{0}

and show that

N

(together with

\vec{A}

) is a weak model of

Γ

in the sense of [39, DEFINITION II.8.9]. It is enough to construct a function

f : S^{Γ} \to 2

which satisfies Tarski's truth definition, where

S^{Γ}

is the set of all substitution instances of subformulas of

Γ

. Let

S_{0}^{Γ}

be the set of all substitution instances of

Σ_{0}^{\vec{A}}

-subformulas of

Γ

. Since there is a

Π_{1}^{\vec{A}} -

formula which defines the truth of all

Σ_{0}^{\vec{A}}

-formulas, one can take a function

f : S_{0}^{Γ} \to 2

which satisfies the truth definition. Then

f

can be expanded to

S^{Γ}

by putting the truth value 1 for all sentences in

S^{Γ} ∖ S_{0}^{Γ}

. (They are

Σ_{1}^{\vec{A}}

Π_{2}^{\vec{A}}

and always true.)

Theorem 5.5. Let

T \supseteq {R C A}_{0}

be an

L_{2}

-theory, and let

Y

be an indicator for

T

For any $r Π_{1}^{1}$ -sentence $φ, T ⊢ φ$ if and only if ${R C A}_{0} + {Y \geq m : m \in N} ⊢ φ$ .
For any $Π_{2}$ -sentence $φ, T ⊢ φ$ if and only if $∣ Σ_{1} + {Y^{i n t} \geq m : m \in ℜ} ⊢ φ .^{12}$

Y

is an indicator for

T

provably in

{W K L}_{0}

, we also have the following:

Over ${R C A}_{0}, r Π_{1}^{1} - corr (T)$ is equivalent to $\forall m Y \geq m$ .
Over $∣ Σ_{1}, Π_{2}$ -corr( $T)$ is equivalent to $\forall m Y^{i n t} \geq m$ .

Proof. We show statements 1 and 3. (Statements 2 and 4 can be shown similarly.)

The right-to-left direction of statement 1 follows from Theorem 5.1.1 and Tanaka's self-embedding theorem [42]. Indeed, if

(M, S)

is a countable nonstandard model of

T

, then there exists a model

(\bar{M}, \bar{S})

which is isomorphic to

(M, S)

such that

M ⊊ e \bar{M}

and

S \subseteq Cod (\bar{M} / M)

. If

X \in S

is infinite in

(M, S)

and

m \in ℜ

, then there exists

\bar{F} \in [\bar{M}]^{< \bar{M}}

such that

X = \bar{F} \cap M

. By the condition (cut),

Y (\bar{F}) \geq m

, hence there exists a set

F \in [M]^{< M}

such that

F \subseteq X

and

Y (F) \geq m

by underspill.

For the left-to-right direction of statement 1 , it is enough to show that if

{\forall x \exists y θ (U, x, y)} \cup {R C A}_{0} \cup {Y \geq m : m \in ℜ}

is consistent with a second-order constant

U

and a

Σ_{0}^{U}

-formula

θ

, then

{\forall x \exists y θ (U, x, y)} \cup T

is consistent. Let

(M, S)

be a countable nonstandard model of

{\forall x \exists y θ (U, x, y)} \cup {R C A}_{0} \cup {Y \geq m : m \in N}

Then there exists an infinite set

A

(M, S)

such that for any

a, b \in A

with

a < b

\forall x < a \exists y < b θ (U, x, y)

. By overspill, there exists an

M

-finite set

F \subseteq A

with

Y (F) \geq m

11 This lemma also follows from (the relativization of) the fact that

I Σ_{1}

is equivalent to

Π_{3}

-corr(EFA). See [1].

12 For statements 1 and 2, the base theories

{R C A}_{0}

and

I Σ_{1}

can be weakened to

{R C A}_{0}^{*}

and

E F A + B Σ_{1}

(the proof still works using recursively saturated models).
for any

m \in ℜ

. By (cut), take

I ⊊ e M

and

S^{'} \subseteq Cod (M / I)

such that

(I, S^{'}) ⊨ T

and

F \cap I

is unbounded in

I

. The latter implies

(I, S^{'}) ⊨ \forall x \exists y θ (U, x, y)

For the left-to-right direction of statement 3 , we first formalize the right-to-left direction of statement 1 within

{W K L}_{0}

. In other words, "for each

m \in N, Y \geq m

is provable in

T

", is provable within

{W K L}_{0}

. Thus it is provable within

{R C A}_{0}

by Theorem 5.1.2 since it is a

Π_{2}^{0}

-statement, and hence

r Π_{1}^{1}

-corr

(T)

implies

\forall m Y \geq m

For the right-to-left direction, again we first work within

{W K L}_{0}

. It is enough to show that if

\forall x \exists y θ (U, x, y)

holds for some set

U

and a

Σ_{0}^{U}

-formula

θ

, then

{\forall x \exists y θ (U, x, y)} \cup T

is consistent. Take an infinite set

A

such that

A

Δ_{1}^{U}

-definable and for any

a, b \in A

with

a < b, \forall x < a \exists y < b θ (U, x, y)

. Then, by the assumption, for any

m \in N

, there exists a finite set

F \subseteq A

such that

Y (F) \geq m

. Thus, by Lemma 5.4, a set of

Π_{2}^{U}

-sentences

Γ = {E F A}^{U} \cup {\forall a \in F \forall b \in F (a < b \to \forall x < a \exists y < b θ (U, x, y))} \cup {Y (F) \geq m : m \in N}

is consistent (consider

F

as a new number constant). Take a countable nonstandard model of

Γ

and formalize the argument for the left-to-right direction of statement 1 , then we see that

{\forall x \exists y θ (U, x, y)} \cup T

is consistent.

The above argument actually showed that for any set

U

, "

\forall m Y \geq m

with respect to any infinite set

A \leq_{T} U^{''}

implies

Σ_{2}^{U}

-corr

(T)

. This is a

Π_{1}^{1}

-statement provable in

W K L_{0}

, so it is also provable within

{R C A}_{0}

by Theorem 5.1.2. Thus

{R C A}_{0}

proves that

\forall m Y \geq m

implies

r Π_{1}^{1} - corr (T)

Theorems 5.3 and 5.5 directly connect

P H

and the correctness statements, and Theorems 2.1 and 2.2 are direct consequences of them. They also imply conservation theorems. Indeed, Theorem 2.6.2 is a direct consequence of Theorems 5.3 and 5.5 plus Theorem 3.8.5 (see

[25]

Proofs of Theorems 3.2-3.6. By definitions,

{\bar{P H}}^{n}, \bar{P H}

, and

I t {\bar{P H}}_{k}^{n}

are equivalent to

variants of

P H

and corresponding

r Π_{1}^{1}

-correctness statements

(1 \leftrightarrow 3

and

2 \leftrightarrow 4

of Theorems 3.2 and

3.3, 1 \leftrightarrow 2

of Theorem

3.4, 1 \leftrightarrow 2 \leftrightarrow 3

of Theorem 3.5 and Theorem 3.6) follow from Theorems 5.3 and 5.5. Implications between variants of

P H

and well-foundedness statements follow from Theorem 3.8 (see the paragraph below Theorem 3.8). Other implications can be shown as follows:

3 \to 5

of Theorem 3.3 and

2 \to 3

of Theorem 3.4 are implied from the formalization of the fact that

{R C A}_{0} + I Σ_{n}^{0}

proves well-foundedness of

ω_{n}^{k}

for each

k \in ℜ

, and

3 \leftrightarrow 4

of Theorem 3.3 is implied from the formalization of the conservation result for

{W K L}_{0} + {R T}^{2}

in [40].

5.3. Indicators corresponding to largeness notions

To obtain a characterization of

r Π_{2}^{1}

-correctness, we modify Theorem 5.5 using indicators which can preserve largeness notions.

Given two finite sets

F_{0} = {x_{0} < \dots < x_{ℓ - 1}}

and

F_{1} = {x_{0}^{'} < \dots < x_{ℓ^{'} - 1}^{'}}

, define

F_{0} ⊴ F_{1}

ℓ \leq ℓ^{'}

and

x_{i} \geq x_{i}^{'}

for any

i < ℓ

. A prelargeness notion

L

is said to be normal if

F_{0} \in L

and

F_{0} ⊴ F_{1}

implies

F_{1} \in L

. It is not difficult to check that

L_{ω}

is a normal largeness
notion. For a given prelargeness notion

L

, put

L^{+} = {F \in L : \forall G \subseteq [0, max F]_{N} (G ⊵ F \to

G \in L)}

. Then

L^{+}

is a normal prelargeness notion.

Lemma 5.6. The following is provable within

{W K L}_{0}

. For any largeness notion

L, L^{+}

is a largeness notion.

Proof. Assume that

L

is a prelargeness notion and there exists an infinite set

X = {x_{0} <

x_{1} < \dots}

such that no finite subset of

X

is a member of

L^{+}

. Define a tree

T \subseteq N < N

σ \in T

if and only if

σ

is strictly increasing,

{σ (i) : i < | σ |} ⊵ {x_{i} : i < | σ |}

and

{σ (i) : i < | σ |} \notin L

. Then,

T

is a bounded tree and

T

is infinite. Take a path

h \in [T]

, then

Y = {h (i) : i \in N}

is an infinite set and any finite subset of

Y

is not a member of

L

Now we generalize the notion of semiregularity with a normal (pre)largeness notion and consider a variant of Theorem 5.5.

Definition 5.2 (

L

-semiregularity). Let

M

be a nonstandard model of

E F A^{L}

, and let

L

be a normal prelargeness notion in

M

. Then, a cut

I \subseteq_{e} M

is said to be

L

-semiregular if for any finite set

F \notin L, F \cap I

is bounded in

I

, or equivalently,

L \cap I

is a normal largeness notion in

(I, Cod (M / I))

Σ_{0}^{\vec{U}}

-formula

Y^{L} \equiv Y (L, F, m)

(where

L \in \vec{U}

) is said to be an

L

-semiregular indicator for an

L_{2}

-theory

T

if for any countable nonstandard model

M ⊨ {E F A}^{V}

with

\vec{U} \subseteq \vec{V}

such that

L

is a normal prelargeness notion in

M, Y^{L}

defines an indicator for

T

M

but the condition (cut) replaced by

(

L

-cut)

Y (F) > m

for any

m \in Ω

if and only if there exists an

L

-semiregular cut

I ⊊ e M

and

S \subseteq Cod (M / I)

such that

(I, S) ⊨ T, U_{i}^{M} \cap I \in S

for each

U_{i} \in \vec{U}

and

F \cap I

is unbounded in

I

Theorem 5.7. Let

T \supseteq {W K L}_{0}

be an

L_{2}

-theory, and let

Y^{L}

be an

L

-semiregular indicator for

T

provably in

{W K L}_{0}

. Then the following assertions are equivalent over

{W K L}_{0}

$r Π_{2}^{1} - corr (T)$ .
For any $L$ , if $L$ is a normal largeness notion, then $\forall m Y^{L} \geq m$ .

Proof. Implication

1 \to 2

follows from the same discussion as the proof for Theorem 5.5. To show

2 \to 1

, we reason within

{W K L}_{0}

and show that, assuming statement 2 is true, if

θ (U)

holds for some set

U

and an

r Π_{1}^{1}

-formula

θ (U)

, then

{θ (U)} \cup T

is consistent. By [34, PROPOSITION 2.5], take a

Σ_{0}^{0}

-formula

η (G, F)

such that

W_{K L}

proves

\forall V (θ (V) \leftrightarrow \forall Z (Z is infinite \to \exists F \subseteq_{fin} Z η (V \cap [0, max F]_{N}, F)))

Define

L_{0} \subseteq [N]^{< N}

G \in L_{0} \leftrightarrow \exists F \subseteq G η (U \cap [0, max F]_{N}, F)

, and let

L = L_{0}^{+}

. Since

θ (U)

holds,

L

is a normal largeness notion. By assumption, we have

Y^{L} \geq m

for any

m \in N

. Thus, by Lemma 5.4 , a set of

Π_{2}^{U, L}

-sentences

Γ = {E F A}^{U, L} \cup {L

is a normal prelargeness notion

} \cup {\forall G (G \in L \to \exists G^{'} η (U \cap {[0, max G^{'}]}_{N}, G^{'}))} \cup {Y^{L} (F) \geq m : m \in N}

is consistent (consider

F

as a new number constant).

Take a countable nonstandard model

M ⊨ Γ

. Then,

M ⊨ Y^{L} (F^{M}) \geq m

for any

m \in N

and thus there exists an

L

-semiregular cut

I ⊊ e M

and

S \subseteq Cod (M / I)

such that

U^{I} = U^{M} \cap I \in S, L^{I} = L^{M} \cap I \in S

and

(I, S) ⊨ T

. Since

I

L^{M}

-semiregular,

L^{I}

is a largeness notion in

(I, S)

. Since

M ⊨ \forall G (G \in L \to \exists G^{'} η (U \cap {[0, max G^{'}]}_{N}, G^{'}))

, we have

(I, S) ⊨ θ (U^{I})

Theorem 5.8. Let

n = 2, 3, 4 \dots

n = \infty

and

k = 2, 3, 4, \dots

k = \infty

. Define

Σ_{0}^{L}

formula

Y_{{I t G P H}_{k}^{n}}^{L}

as follows:

within

{W K L}_{0}

Proof. Essentially the same as the proof for Theorem 5.3.3. We additionally need to show the following (which is an analogous of (i)'):

L

is a normal prelargeness notion,

F

ℓ + 1

-dense

(n, k, L \cap L_{ω})

with

ℓ \geq 1

and

G

is a finite set such that

G \notin L

, then there exists

F^{'} \subseteq F

such that

F^{'}

ℓ

-dense

(n, k, L \cap L_{ω})

and

{[min F^{'}, max F^{'})}_{N} \cap G = \emptyset

Given

ℓ, L, F

and

G

as above, define

c : [F]^{2} \to 2

c ({x, y}) = 1 \leftrightarrow [x, y)_{N} \cap G \neq \emptyset

. Take a

c

-homogeneous set

F^{'} \subseteq F

such that

F^{'}

ℓ

-dense

(n, k, L \cap L_{ω})

. If

{[F^{'}]}^{2} \subseteq c^{- 1} (0)

, we are done, so assume

{[F^{'}]}^{2} \subseteq c^{- 1} (1)

. Put

G^{'} = G \cap {[min F^{'}, max F^{'})}_{N}

and

F^{''} = F^{'} ∖ {min F^{'}}

. Then

F^{''}

is at least 0 -dense

(n, k, L \cap L_{ω})

and thus

F^{''} \in L

. On the other hand,

G^{'} ⊵ F^{''}

by the definition of

c

, and thus

G^{'} \in L

. This is a contradiction since

G^{'} \subseteq G

and

G \notin L

Proofs of Theorems 4.6, 4.7, and 4.8. By Lemma 5.6,

{I t G P H}_{k}^{n}

is equivalent to the statement

ACKNOWLEDGMENTS

It is a pleasure to thank Leszek KoÅ‚odziejczyk for careful reading of the manuscript and helpful discussions and comments, and to Kazuyuki Tanaka for helpful suggestions and advice.

FUNDING

This work is partially supported by JSPS KAKENHI grant number 19K03601.

REFERENCES

[1] L. Beklemishev, Reflection principles and provability algebras in formal arithmetic. Russian Math. Surveys 60 (2005).

[2] L. Bienvenu, L. Patey, and P. Shafer, On the logical strengths of partial solutions to mathematical problems. Trans. Lond. Math. Soc. 4 (2017), no. 1, 30-71.

[3] T. Bigorajska and H. Kotlarski, A partition theorem for

α

-large sets. Fund. Math. 160 (1999), no. 1, 27-37.

[4] T. Bigorajska and H. Kotlarski, Some combinatorics involving

ξ

-large sets. Fund. Math. 175 (2002), no. 2, 119-125.

[5] T. Bigorajska and H. Kotlarski, Partitioning

α

-large sets: some lower bounds. Trans. Amer. Math. Soc. 358 (2006), no. 11, 4981-5001.

[6] A. Bovykin and A. Weiermann, The strength of infinitary Ramseyan principles can be accessed by their densities. Ann. Pure Appl. Logic 168 (2017), no. 9,

1700 - 1709

[7] P. A. Cholak, C. G. Jockusch, and T. A. Slaman, On the strength of Ramsey's theorem for pairs. J. Symbolic Logic 66 (2001), no. 1, 1-15.

[8] C. T. Chong, T. A. Slaman, and Y. Yang, The metamathematics of Stable Ramsey's Theorem for Pairs. J. Amer. Math. Soc. 27 (2014), no. 3, 863-892.

[9] D. D. Dzhafarov, D. R. Hirschfeldt, and S. C. Reitzes, Reduction games, provability, and compactness. 2020, arXiv:2008.00907.

[10] M. Fiori Carones, L. A. KoÅ‚odziejczyk, T. L. Wong, and K. Yokoyama, An isomorphism theorem for models of weak KÃ´nig's lemma without primitive recursion. 2021, arXiv:2112.10876.

[11] S. Flood, Reverse mathematics and a Ramsey-type KÃ³nig's lemma. J. Symbolic Logic 77 (2012), no. 4, 1272-1280.

[12] S. Flood and H. Towsner, Separating principles below WKL

{W L}_{0}

MLQ Math. Log.

Q

. 62 (2016), no. 6, 507-529.

[13] H. M. Friedman, K. McAloon, and S. G. Simpson, A finite combinatorial principle which is equivalent to the 1-consistency of predicative analysis. In Patras Logic Symposion (Patras, 1980), pp. 197-230, Stud. Logic Found. Math. 109, North-Holland, Amsterdam-New York, 1982.

[14] J. Gaspar and U. Kohlenbach, On Tao's "finitary" infinite pigeonhole principle. J. Symbolic Logic 75 (2010), no. 1, 355-371.

[15] R. L. Goodstein, On the restricted ordinal theorem. J. Symbolic Logic 9 (1944), 33-41.

[16] P. HÃ¡jek and P. PudlÃ¡k, Metamathematics of first-order arithmetic. Perspect. Math. Log., Springer, Berlin, 1998.

[17] D. R. Hirschfeldt, Slicing the truth. Lect. Notes Ser. 28, Institute for Mathematical Sciences, National University of Singapore, 2014.

[18] J. L. Hirst, Combinatorics in subsystems of second order arithmetic. Ph.D. thesis, The Pennsylvania State University, 1987.

[19] C. G. Jockusch, Ramsey's theorem and recursion theory. J. Symbolic Logic 37 (1972), no. 2, 268-280.

[20] A. Kanamori and K. McAloon, On GÃ¶del incompleteness and finite combinatorics. Ann. Pure Appl. Logic 33 (1987), no. 1, 23-41.

[21] R. Kaye, Models of Peano arithmetic. Oxford University Press, 1991.

[22] J. Ketonen and R. Solovay, Rapidly growing Ramsey functions. Ann. of Math. (2) 113 (1981), no. 2, 267-314.

[23] L. A. S. Kirby and J. B. Paris, Initial segments of models of Peano's axioms. In Set theory and hierarchy theory V (Proc. Third Conf., Bierutowice, 1976), pp. 211-226, Lecture Notes in Math. 619, Springer, Berlin, 1977.

[24] L. A. KoÅ‚odziejczyk, T. L. Wong, and K. Yokoyama, Ramsey's theorem for pairs, collection, and proof size. 2021, arXiv:2005.06854v2.

[25] L. A. KoÅ‚odziejczyk and K. Yokoyama, Some upper bounds on ordinal-valued Ramsey numbers for colourings of pairs. Selecta Math. (N.S.) 26 (2020), no. 4, 56,

18 p p

[26] R. Kossak and J. H. Schmerl, The structure of models of Peano arithmetic. Oxford Logic Guides 50, Oxford University Press, Oxford, 2006.

[27] H. Kotlarski, B. Piekart, and A. Weiermann, More on lower bounds for partitioning

α

-large sets. Ann. Pure Appl. Logic 147 (2007), no. 3, 113-126.

[28] J. Liu, RT 2 does not imply WKL . J. Symbolic Logic 77 (2012), no. 2, 609-620.

[29] K. McAloon, Paris-Harrington incompleteness and progressions of theories. In Recursion theory (Ithaca, NY, 1982), pp. 447-460, Proc. Sympos. Pure Math. 42, Amer. Math. Soc., Providence, RI, 1985.

[30] B. Monin and L. Patey, SRT22 does not imply RT22 in omega-models. 2019, arXiv:1905.08427v3.

[31] F. Pakhomov and J. Walsh, Reflection ranks and ordinal analysis. 2019, arXiv:1805.02095v2.

[32] J. B. Paris, Some independence results for Peano arithmetic. J. Symbolic Logic 43 (1978), no. 4, 725-731.

[33] J. Paris and L. Harrington, A mathematical incompleteness in Peano arithmetic. In Handbook of mathematical logic, edited by J. Barwise, pp. 1133-1142, Stud. Logic Found. Math. 90, North-Holland, Amsterdam, 1977.

[34] L. Patey and K. Yokoyama, The proof-theoretic strength of Ramsey's theorem for pairs and two colors. Adv. Math. 330 (2018), 1034-1070.

[35] F. Pelupessy, Phase transition results for three Ramsey-like theorems. Notre Dame J. Form. Log. 57 (2016), no. 2, 195-207.

[36] F. Pelupessy, On the "finitary" Ramsey's theorem. 2016, arXiv:1508.02013v7.

[37] D. Seetapun and T. A. Slaman, On the strength of Ramsey's theorem. Notre Dame J. Form. Log. 36 (1995), no. 4, 570-582.

[38] S. G. Simpson, Unprovable theorems and fast-growing functions. In Logic and combinatorics (Arcata, CA, 1985), pp. 359-394, Contemp. Math. 65, Amer. Math. Soc., Providence, RI, 1987.

[39] S. G. Simpson, Subsystems of second order arithmetic. Perspect. Math. Log., Springer, Berlin, 1999.

[40] T. A. Slaman and K. Yokoyama, The strength of Ramsey's theorem for pairs and arbitrarily many colors. J. Symbolic Logic

83

(2018), no. 4, 1610-1617.

[41] M. D. Smet and A. Weiermann, Partitioning

α

-large sets for

α < ε_{ω}

. 2010, arXiv:1001.2437.

[42] K. Tanaka, The self-embedding theorem of

{W K L}_{0}

and a non-standard method. Ann. Pure Appl. Logic 84 (1997), no. 1, 41-49.

[43] T. Tao, Soft analysis, hard analysis, and the finite convergence principle. http:// terrytao.wordpress.com, 2007, appeared in T. Tao, Structure and randomness: pages from year one of a mathematical blog. American Mathematical Society, 2008,

298 p p

[44] A. Weiermann, A classification of rapidly growing Ramsey functions. Proc. Amer. Math. Soc. 132 (2004), no. 2, 553-561.

[45] K. Yokoyama, Unpublished note.

[46] K. Yokoyama, On the strength of Ramsey's theorem without

Σ_{1}

-induction.

M L Q

Math. Log. Q. 59 (2013), no. 1-2, 108-111.

KEITA YOKOYAMA

Mathematical Institute, Tohoku University, 6-3, Aramaki Aza-Aoba, Aoba-ku, Sendai 9808578, Japan, keita.yokoyama.c2@ tohoku.ac.jp

CONSTRAINT SATISFACTION PROBLEM: WHAT MAKES THE PROBLEM EASY

DMITRIY ZHUK

Abstract

The Constraint Satisfaction Problem is the problem of deciding whether there is an assignment to a set of variables subject to some specified constraints. Systems of linear equations, graph coloring, and many other combinatorial problems can be expressed as Constraint Satisfaction Problems for some constraint language. In 1993 it was conjectured that for any constraint language the problem is either solvable in polynomial time, or NPcomplete, and for many years this conjecture was the main open question in the area. After this conjecture was resolved in 2017, we finally can say what makes the problem hard and what makes the problem easy. In the first part of the paper, we give an elementary introduction to the area, explaining how the full classification appeared and why it is formulated in terms of polymorphisms. We discuss what makes the problem NP-hard, what makes the problem solvable by local consistency checking, and explain briefly the main idea of one of the two proofs of the conjecture. The second part of the paper is devoted to the extension of the CSP, called Quantified CSP, where we allow using both universal and existential quantifiers. Finally, we discuss briefly other variants of the CSP, as well as some open questions related to them.

MATHEMATICS SUBJECT CLASSIFICATION 2020

Primary 3B70; Secondary 08A70, 68Q17, 03D15, 68T27, 03B10

KEYWORDS

Constraint satisfaction problem, computational complexity, CSP dichotomy, quantified constraints

1. INTRODUCTION

Probably the main question in theoretical computer science is to understand why some computational problems are easy (solvable in polynomial time) while others are difficult (NP-hard, PSpace-hard, and so on). What is the difference between P and NP? Why a system of linear equations can be solved in polynomial time by the Gaussian elimination but we cannot check whether a graph is 3-colorable in polynomial time (if we believe that

P \neq N P)

. What is the principal difference between these two problems? To work on this question, first we would like to classify the problems by whether they are solvable in polynomial time (tractable) or NP-complete. Even for very simple decision problems, sometimes we do not know the answer.

For example, a system of linear equations in

Z_{2}

can be solved by Gaussian elimination, but if we are allowed to add one linear equation with usual sum for integers then the problem becomes NP-complete [26]. Surprisingly, the complexity is not known if we can add one equation modulo 24 to a system of linear equations in

Z_{2}

(variables are still from

{0, 1})

[17]. In the paper we give a formal definition to such problems and discuss why some of them can be solved in polynomial time, while others are NP-hard.

2. CONSTRAINT SATISFACTION PROBLEM

The above problems are known as the Constraint Satisfaction Problem (CSP), which is the problem of deciding whether there is an assignment to a set of variables subject to some specified constraints. Formally, the Constraint Satisfaction Problem is defined as a triple

⟨ X, D, C ⟩

, where

$X = {x_{1}, \dots, x_{n}}$ is a set of variables,
$D = {D_{1}, \dots, D_{n}}$ is a set of the respective domains,
$C = {C_{1}, \dots, C_{m}}$ is a set of constraints,

where each variable

x_{i}

can take on values in the nonempty domain

D_{i}

, every constraint

C_{j} \in C

is a pair

(t_{j}, R_{j})

where

t_{j}

is a tuple of variables of length

m_{j}

, called the constraint scope, and

R_{j}

is an

m_{j}

-ary relation on the corresponding domains, called the constraint relation.

The question is whether there exists a solution to

⟨ X, D, C ⟩

, that is, a mapping that assigns a value from

D_{i}

to every variable

x_{i}

such that for each constraint

C_{j}

the image of the constraint scope is a member of the constraint relation.

To simplify the presentation, we assume that the domain of every variable is a finite set

A

. We also assume that all the relations are from a set

Γ

, which we call the constraint language. Then the Constraint Satisfaction Problem over a constraint language

Γ

, denoted

CSP (Γ)

, is the following decision problem: given a conjunctive formula

R_{1} (v_{1, 1}, \dots, v_{1, n_{1}}) \land \dots \land R_{s} (v_{s, 1}, \dots, v_{s, n_{s}})

where

R_{1}, \dots, R_{s} \in Γ

, and

v_{i, j} \in {x_{1}, \dots, x_{n}}

for every

i, j

, decide whether this formula is satisfiable. Note that in the paper we do not distinguish between relations and predicates, and in the previous formula we write relations meaning predicates.

2.1. Examples

It is well known that many combinatorial problems can be expressed as

CSP (Γ)

for some constraint language

Γ

. Moreover, for some

Γ

the corresponding decision problem can be solved in polynomial time; while for others it is NP-complete. It was conjectured that

CSP (Γ)

is either in

P

or NP-complete [29]. Let us consider several examples.

System of linear equations. Let

A = {0, 1}

and

Γ = {a_{1} x_{1} + a_{2} x_{2} + \dots + a_{k} x_{k} = a_{0} ∣ a_{0}, a_{1}, \dots, a_{k} \in Z_{2}}

i.e.,

Γ

consists of all linear equations in the field

Z_{2}

. Then

CSP (Γ)

is equivalent to the problem of solving a system of linear equations, which is solvable by the Gaussian elimination in polynomial time, thus,

CSP (Γ)

is in

P

Graph 2-coloring. To color a graph using two colors, we just need to choose a color of every vertex so that adjacent vertices have different colors. We assign a variable to each vertex, and encode the two colors with 0 and 1. For an edge between the

i

th and

j

th vertices, we add the constraint

x_{i} \neq x_{j}

. For instance, the 5 -cycle is equivalent to the CSP instance

(x_{1} \neq x_{2}) \land (x_{2} \neq x_{3}) \land (x_{3} \neq x_{4}) \land (x_{4} \neq x_{5}) \land (x_{5} \neq x_{1})

Hence, the problem of graph 2-coloring is equivalent to

CSP (Γ)

for

A = {0, 1}

and

Γ = {\neq}

. This problem can be solved locally. We choose a color of some vertex, then we color their neighbors with a different color, and so on. Either we will color all the vertices, or we will find an odd cycle, which means that the graph is not colorable using two colors. Thus, this problem is solvable in polynomial time.

Graph 3-coloring. Similarly, the problem of coloring a graph using 3 colors is equivalent to

CSP (Γ)

for

A = {0, 1, 2}

and

Γ = {\neq}

. Unlike the graph 2-coloring, this problem is known to be NP-complete [1].

NAE-satisfability and 1IN3-satisfability. Suppose

A = {0, 1}

. NAE is the ternary notall-equal relation, that is, NAE

= {0, 1}^{3} ∖ {(0, 0, 0), (1, 1, 1)}

. 1IN3 is the ternary 1-in-3 relation, that is,

1 IN 3 = {(0, 0, 1), (0, 1, 0), (1, 0, 0)}

. As it is known [40], both

CSP ({N A E})

and

CSP ({1 I N 3})

are NP-complete.

The main goal of this paper is to explain why the first two examples are in

P

, while the others are NP-hard.

2.2. Reduction from one language to another

To prove the hardness result, we usually reduce a problem to a known NP-hard problem. Let us show how we can go from one constraint language to another.

CSP (Γ)

can be
viewed as the problem of evaluating a sentence

\begin{matrix} (2.1) & \exists x_{1} \dots \exists x_{n} (R_{1} (v_{1, 1}, \dots, v_{1, n_{1}}) \land \dots \land R_{s} (v_{s, 1}, \dots, v_{s, n_{s}})) \end{matrix}

where all variables are existentially quantified. Hence, if we could express one language using conjunctions and existential quantifiers from another language, then we get a reduction from one CSP to another. Let us explain how it works on a concrete example.

Let NA1

= {0, 1}^{3} ∖ {(1, 1, 1)}

, that is, a ternary relation that holds whenever not all elements are 1. Let

A = {0, 1}, Γ_{1} = {N A 1, \neq}

, and

Γ_{2} = {1 I N 3}

. Let us show that

CSP (Γ_{1})

and

CSP (Γ_{2})

are (polynomially) equivalent. We may check that

\begin{matrix} (2.2) & (x \neq y) = \exists u \exists v 1 IN 3 (x, y, u) \land 1 IN 3 (u, u, v) \end{matrix}

If fact, from

IIN 3 (u, u, v)

we derive that

u = 0

, hence

x \neq y

. Similarly, we have

\begin{aligned} NA 1 (x, y, z) = \exists & x^{'} \exists y^{'} \exists z^{'} \exists x^{''} \exists y^{''} \exists z^{''} 1 IN 3 (x^{'}, y^{'}, z^{'}) \\ (2.3) & \land 1 IN 3 (x, x^{'}, x^{''}) \land 1 IN 3 (y, y^{'}, y^{''}) \land 1 IN 3 (z, z^{'}, z^{''}) \end{aligned}

x = y = z = 1

, then

x^{'} = y^{'} = z^{'} = 0

, which contradicts

1 IN 3 (x^{'}, y^{'}, z^{'})

. In all other cases, we can find an appropriate assignment.

Any instance of

CSP (Γ_{1})

can be reduced to an instance of

CSP (Γ_{2})

in the following way. We replace each constraint

(x_{i} \neq x_{j})

by the right-hand side of (2.2) introducing two new variables. Also, we replace each constraint NA1

(x_{i}, x_{j}, x_{k})

by the right-hand side of (2.3) introducing six new variables. This reduction is obviously polynomial (and even log-space). Similarly, we have

\begin{array}{r} IIN3 (x, y, z) = \exists x^{'} \exists y^{'} \exists z^{'} (NA 1 (x, y, y) \land NA 1 (y, z, z) \land NA 1 (z, x, x) \\ \land (x \neq x^{'}) \land (y \neq y^{'}) \land (z \neq z^{'}) \land NA1 (x^{'}, y^{'}, z^{'})) \end{array}

which implies a polynomial reduction from

CSP (Γ_{2})

CSP (Γ_{1})

Let us give a formal definition for the above reduction. A formula of the form

\exists y_{1} \dots \exists y_{n} Φ

, where

Φ

is a conjunction of relations from

Γ

is called a positive primitive formula (pp-formula) over

Γ

. If

R (x_{1}, \dots, x_{n}) = \exists y_{1} \dots \exists y_{n} Φ

, then we say that

R

p p

defined by this formula, and

\exists y_{1} \dots \exists y_{n} Φ

is called its

p p

-definition.

Theorem 2.1 ([35]). Suppose

Γ_{1}

and

Γ_{2}

are finite constraint languages such that each relation from

Γ_{1}

is pp-definable over

Γ_{2}

. Then

CSP (Γ_{1})

is polynomial time reducible to

CSP (Γ_{2})

2.3. Polymorphisms as invariants

If we can pp-define a relation

R

from a constraint language

Γ

and

CSP ({R})

is NP-hard, then

CSP (Γ)

is also NP-hard. How to show that such a relation cannot be ppdefined? To prove that something cannot be done, we usually find some fundamental property (invariant) that is satisfied by anything we can obtain. For the relations, the operations play the role of invariants.

We say that an operation

f : A^{n} \to

A preserves a relation

R

of arity

m

if for any tuples

(a_{1, 1}, \dots, a_{1, m}), \dots, (a_{n, 1}, \dots, a_{n, m}) \in R

the tuple

(f (a_{1, 1}, \dots, a_{n, 1}), \dots, f (a_{1, m}, \dots, a_{n, m}))

is in

R

. In this case we also say that

f

is a polymorphism of

R

, and

R

is an invariant of

f

. We say that an operation preserves a set of relations

Γ

if it preserves every relation in

Γ

. In this case we also write

f

is a polymorphism of

Γ

f \in Pol (Γ)

. It can be easily checked that if

f

preserves

Γ

, then

f

preserves any relation

R

pp-definable from

Γ

. Moreover, we can show

[15, 31]

that

Pol (Γ_{1}) \subseteq Pol (Γ_{2})

if and only if

Γ_{2}

is pp-definable over

Γ_{1}

, which means that the complexity of

CSP (Γ)

depends only on

Pol (Γ)

Example 1. Let

R

be the linear order relation on

{0, 1, 2}

, i.e.,

R = (\begin{array}{llllll} 0 & 0 & 0 & 1 & 1 & 2 \\ 0 & 1 & 2 & 1 & 2 & 2 \end{array})

where columns are tuples from the relation. Then "an

n

-ary operation

f

preserves

R

" means that for all

(\binom{a_{1}}{b_{1}}), \dots, (\binom{a_{n}}{b_{n}}) \in R

that is,

a_{i} \leq b_{i}

, we have

f (\begin{array}{llll} a_{1} & a_{2} & \dots & a_{n} \\ b_{1} & b_{2} & \dots & b_{n} \end{array}) := (\binom{f (a_{1}, \dots, a_{n})}{f (b_{1}, \dots, b_{n})}) \in R

that is,

f (a_{1}, \dots, a_{n}) \leq f (b_{1}, \dots, b_{n})

. In other words,

f

is monotonic. For instance, the operations max and min are monotonic. By the above observation, we know that any relation pp-definable from

R

is also preserved by min and max.

Example 2. Let

A = {0, 1}

. Let us show that 1IN3 cannot be pp-defined from NA1 and

x \leq y

. We can check that the conjunction

x \land y

(an operation on

{0, 1}

) preserves both NA1 and

x \leq y

. However,

x \land y

does not preserve 1IN3 as we have

(\begin{array}{l} 1 \\ 0 \\ 0 \end{array}) \land (\begin{array}{l} 0 \\ 1 \\ 0 \end{array}) = (\begin{array}{l} 0 \\ 0 \\ 0 \end{array}) \notin 1 I N 3

For more information on polymorphisms and how they can be used to study the complexity of the CSP, see [6].

2.4. Local consistency

The first step of almost any algorithm solving a CSP instance is checking local consistency. For instance, if a constraint forces a variable to be equal to 0 , then we could substitute 0 and remove this variable.

Suppose we have a CSP instance

\begin{matrix} (2.4) & R_{1} (v_{1, 1}, \dots, v_{1, n_{1}}) \land \dots \land R_{s} (v_{s, 1}, \dots, v_{s, n_{s}}) \end{matrix}

This instance is called 1 -consistent (also known as arc-consistent), if for any variable

x

any two constraints

R_{i} (v_{i, 1}, \dots, v_{i, n_{i}})

and

R_{j} (v_{j, 1}, \dots, v_{j, n_{j}})

having this variable in the scope have the same projection onto this variable. This means that for every variable

x

there exists

D_{x} \subseteq A

, called the domain of

x

, such that the projection of any constraint on

x

D_{x}

Sometimes we need a stronger consistency (similar to singleton-arc-consistency in [36]). We say that

z_{1} - C_{1} - z_{2} - \dots - C_{l - 1} - z_{l}

is a path in a CSP instance

d

z_{i}, z_{i + 1}

are in the scope of the constraint

C_{i}

for every

i \in {1, 2, \dots, l - 1}

. We say that

a

path

z_{1} - C_{1} - z_{2} - \dots - C_{l - 1} - z_{l}

connects

b

and

c

if there exist

a_{1}, a_{2}, \dots, a_{l} \in A

such that

a_{1} = b, a_{l} = c

, and the projection of each

C_{i}

onto

z_{i}, z_{i + 1}

contains the tuple

(a_{i}, a_{i + 1})

. A CSP instance

d

is called cycle-consistent if it is 1-consistent and for every variable

z

and

a \in D_{z}

any path starting and ending with

z

ℓ

connects

a

and

a

It is not hard to find a polynomial procedure making the instance 1-consistent or cycle-consistent. For 1-consistency, the idea is to find a variable where the consistency is violated, then reduce the domain

D_{x}

of this variable and reduce the corresponding relations. We repeat this while some constraints violate consistency. Finally, we either get a 1-consistent instance, or we get a contradiction (derive that

D_{x} = \emptyset

). For cycle-consistency, we should go deeper. For every variable

x

and every value

a \in D_{x}

, we reduce the domain of

x

{a}

and check whether the remaining instance can be made 1-consistent. If not, then

x

cannot be equal to

a

, and

a

can be excluded from the domain

D_{x}

Later we will show that in some cases 1-consistency and cycle-consistency are enough to solve a CSP instance, that is, any consistent instance has a solution. See [5, 36] for more information about local consistency conditions.

2.5. CSP over a 2-element domain

The complexity of

CSP (Γ)

for each constraint language

Γ

{0, 1}

was described in 1978 [40]. This classification can be formulated nicely using polymorphisms.

Theorem 2.2 ([34,40]). Suppose

A = {0, 1}, Γ

is a constraint language on

A

. Then

CSP (Γ)

is solvable in polynomial time if

(1) 0 preserves

Γ

, or

(2) 1 preserves

Γ

, or

(3)

x \lor y

preserves

Γ

, or

(4)

x \land y

preserves

Γ

, or

(5)

x y \lor y z \lor x z

preserves

Γ

, or

(6)

x + y + z

preserves

Γ

CSP (Γ)

is NP-complete otherwise.

Let us consider each case and explain how the polymorphisms make the problem easy. Note that the cases (1) and (2), (3) and (4) are dual to each other, that is why we consider only one in each pair in detail.

0

preserves

Γ

. This case is almost trivial. "The constant 0 preserves a relation

R \in Γ

" means that

R (0, 0, \dots, 0)

holds. If 0 preserves all relations from

Γ

, then

(0, 0, \dots, 0)

is always a solution of a

CSP

instance, which makes the problem

CSP (Γ)

trivial.

x \lor y

preserves

Γ

. Let us show how to solve an instance of

CSP (Γ)

x \lor y \in Pol (Γ)

. First, we make our instance 1-consistent. Then, unless we get a contradiction, every variable

x

has its domain

D_{x}

which is either

{0}

, or

{1}

, or

{0, 1}

. We claim that if we send the variables with domain

{0}

to 0 , and the variables with the domain

{1}

and

{0, 1}

to 1 , then we get a solution. In fact, if we apply

x \lor y

to all the tuples of some constraint, we obtain a tuple consistent with the solution. Thus, 1-consistency guarantees the existence of a solution in this case.

x y \lor y z \lor x z

preserves

Γ

. The operation

x y \lor y z \lor x z

returns the most popular value and is known as a majority operation. It is not hard to check [2] that any relation preserved by a majority operation can be represented as a conjunction of binary relations, and we may assume that

Γ

consists of only binary relations. As it is shown in Section 2.8, for a 2-element domain this gives a polynomial algorithm for

CSP (Γ)

. Additionally, we can show

[36, 47]

that any cycle-consistent instance of

CSP (Γ)

has a solution. Hence to solve an instance, it is sufficient to make it cycle-consistent, and unless we obtain an empty domain (contradiction) the instance has a solution.

x + y + z

preserves

Γ

. It is known (see Lemma 2.8) that

x + y + z

preserves a relation

R

if and only if the relation

R

can be represented as a conjunction of linear equations. Thus,

CSP (Γ)

is equivalent to the problem of solving of a system of linear equations in the field

Z_{2}

, which is tractable.

2.6. CSP solvable by local consistency checking

As we see in the previous section all tractable CSPs on a 2-element domain can be solved by two algorithms. The first algorithm just checks some local consistency (1-consistency, cycle-consistency) and, if a sufficient level of consistency achieved, we know that the instance has a solution. The second algorithm is the Gaussian elimination applied to a system of linear equations. In this section we discuss when the first algorithm is sufficient and why some instances can be solved by a local consistency checking, while others require something else.

To simplify the presentation in this section, we assume that all constant relations

x = a

are in the constraint language. In this case any polymorphism

f

Γ

is idempotent, that is,

f (x, x, \dots, x) = x

. This restriction does not affect the generality of the results because we can always consider the core of the constraint language and then add all constant relations
(see [34]). Consider the following system of linear equations in

Z_{p}

\begin{matrix} (2.5) & {\begin{cases} x_{1} + x_{2} = x_{3} + 0 \\ x_{3} + 0 = x_{4} + x_{5} \\ x_{4} + 0 = x_{1} + x_{6} \\ x_{5} + x_{6} = x_{2} + 1 \end{cases} \end{matrix}

If we calculate the sum of all equations, we will get

0 = 1

, which means that the system does not have a solution. Nevertheless, we may check that the system is cycle-consistent, which means that the cycle-consistency does not guarantee the existence of a solution for linear equations. In fact, we can show that there does not exist a local consistency condition that guarantees the existence of a solution of a system of linear equations (see [5]).

As it was shown in

[5, 47]

CSP (Γ)

cannot be solved by cycle-consistency checking then we can express a linear equation modulo

p

using

Γ

. Since our constraint language is on a domain

A

, we could not expect to pp-define the relation

x_{1} + x_{2} = x_{3} + x_{4} (mod p)

. Instead, we claim that there exist

S \subseteq A

and a surjective mapping

φ : A \to Z_{p}^{s}

such that the relation

\begin{matrix} (2.6) & {(a_{1}, a_{2}, a_{3}, a_{4}} ∣ a_{1}, a_{2}, a_{3}, a_{4} \in S, φ (a_{1}) + φ (a_{2}) = φ (a_{3}) + φ (a_{4})} \end{matrix}

is pp-definable. This means that the linear equation is defined on some

S

modulo some equivalence relation defined by

φ

. To avoid such a transformation, we could introduce the notion of pp-constructability and say that

x_{1} + x_{2} = x_{3} + x_{4} (mod p)

is pp-constructable from

Γ

. To keep everything simple, we do not define pp-constructability and use it informally hoping that the idea of this notion is clear from our example. For more details about pp-constructability, see [7].

If such a linear equation cannot be pp-defined (pp-constructed) then there should be some operation that preserves

Γ

but not the linear equation modulo

p

. An operation

f

is called

a

Weak Near Unanimity Operation (WNU) if it satisfies the following identity:

f (y, x, x, \dots, x) = f (x, y, x, \dots, x) = \dots = f (x, x, \dots, x, y)

It is not hard to check that an idempotent

W N U

of arity

p

does not preserve a nontrivial linear equation modulo

p

(see Lemma 4.9 in [47]). Thus, the existence of an idempotent

p

-ary WNU polymorphism of

Γ

guarantees that a linear equation modulo

p

cannot be

p p

defined (pp-constructed). That is why a relation satisfying (2.6) is called

p

-WNU-blocker Hence, if

Γ

has WNU polymorphisms of all arities then no linear equations can appear. The following theorem confirms that nothing but linear equations could be an obstacle for the local consistency checking.

Theorem 2.3 ([47]). Suppose

Γ

is a constraint language containing all constant relations. The following conditions are equivalent:

(1) every cycle-consistent instance of

CSP (Γ)

has a solution;

(2)

Γ

has a WNU polymorphisms of all arities

n \geq 3

;

(3) there does not exist a

p

-WNU-blocker pp-definable from

Γ

Thus, the fact that we cannot express (pp-define, pp-construct) a nontrivial linear equation makes the problem solvable by the cycle-consistency checking.

2.7. CSP Dichotomy Conjecture

In this subsection, we formulate a criterion for

CSP (Γ)

to be solvable in polynomial time. This criterion is known as the CSP Dichotomy Conjecture, it was formulated almost 30 years ago [28,29] but was an open question until 2017 [19,20,42,44].

Theorem 2.4 (

[19, 20, 42, 44])

. Suppose

Γ

is a constraint language on a finite set

A

. Then

(1)

CSP (Γ)

is solvable in polynomial time if

Γ

is preserved by a

W N U

;

(2)

CSP (Γ)

is NP-complete otherwise.

The reason why the existence of a WNU polymorphism makes the problem easy is the fact that we cannot pp-define a strong relation giving us NP-hardness. A relation

R = {(B_{0} \cup B_{1})}^{3} ∖ (B_{0}^{3} \cup B_{1}^{3})

, where

B_{0}, B_{1} \subseteq A, B_{0} \neq \emptyset, B_{1} \neq \emptyset

, and

B_{0} \cap B_{1} = \emptyset

, is called a WNU-blocker. Such relations are similar to the not-all-equal (NAE) relation on

{0, 1}

, where

B_{0}

means 0 and

B_{1}

means 1 . Instead of the existence of a pp-definable WNU-blocker, we could say that the relation NAE is pp-constructable from

Γ

. Note that

CSP ({N A E})

and

CSP ({R})

for a WNU-blocker

R

are NP-complete problems.

We can check (see Lemma 4.8 in [47]) that a WNU operation does not preserve a WNU-blocker. Moreover, we have the following criterion.

Lemma 2.5 ([47]). A constraint language

Γ

containing all constant relations is preserved by a WNU if and only if there is no WNU-blocker pp-definable from

Γ

Thus,

CSP (Γ)

is solvable in polynomial time if and only if a WNU-blocker cannot be pp-defined. Hence, the fact that we cannot pp-construct the not-all-equal relation makes the problem easy, and a

W N U

is an operation that guarantees that this relation cannot be pp-constructed.

2.8. How to solve CSP if pp-definable relations are simple

Below we discuss how the fact that only simple relations can be pp-defined from

Γ

can help to solve

CSP (Γ)

in polynomial time. In this case we can calculate the sentence explicitly eliminating existential quantifiers one by one. I believe that a similar idea should work for any

Γ

preserved by a WNU, which will give us a simple algorithm for

CSP (Γ)

CSP (Γ)

can be viewed as the following problem. Given a sentence

\exists x_{1} \dots \exists x_{n} (R_{1} (v_{1, 1}, \dots, v_{1, n_{1}}) \land \dots \land R_{s} (v_{s, 1}, \dots, v_{s, n_{s}}))

we need to check whether it holds. To do this, let us remove the quantifiers one by one. Let

Δ_{n - 1} (x_{1}, \dots, x_{n - 1}) = \exists x_{n} (R_{1} (v_{1, 1}, \dots, v_{1, n_{1}}) \land \dots \land R_{s} (v_{s, 1}, \dots, v_{s, n_{s}}))

In general,

Δ_{n - 1}

could be any relation of arity

n - 1

, and even to write this relation we need

| A |^{n - 1}

bits. Nevertheless, we believe that if

CSP (Γ)

is tractable then the relation

Δ_{n - 1}

(or
the important part of it) has a compact representation and can be efficiently computed. Then we calculate

Δ_{n - 2}, Δ_{n - 3}, \dots, Δ_{0}

, where

Δ_{i - 1} (x_{1}, \dots, x_{i - 1}) = \exists x_{i} Δ_{i} (x_{1}, \dots, x_{i})

, and the value of

Δ_{0}

is the answer we need.

We may check that on a 2-element domain we have

\begin{aligned} \exists x_{n} (R_{1} (v_{1, 1}, \dots, v_{1, n_{1}}) \land \dots \land R_{s} (v_{s, 1}, \dots, v_{s, n_{s}})) \\ (2.7) & = \underset{i, j \in {1, 2, \dots, s}}{⋀} (\exists x_{n} R_{i} (v_{i, 1}, \dots, v_{i, n_{i}}) \land R_{j} (v_{j, 1}, \dots, v_{j, n_{j}})) \end{aligned}

The implication

\Rightarrow

is obvious. To prove

\Leftarrow

assume that the left-hand side does not hold. Then the conjunctive part does not hold on both

(x_{1}, \dots, x_{n - 1}, 0)

and

(x_{1}, \dots, x_{n - 1}, 1)

. Hence, there exist

i

and

j

such that

R_{i} (v_{i, 1}, \dots, v_{i, n_{i}})

does not hold on

(x_{1}, x_{2}, \dots, x_{n - 1}, 0)

and

R_{j} (v_{j, 1}, \dots, v_{j, n_{j}})

does not hold on

(x_{1}, x_{2}, \dots, x_{n - 1}, 1)

. Hence, the

(i, j)

-part of the righthand side does not hold.

There are two problems if we use (2.7) to solve the CSP. First, as we mentioned above, the relation

R_{i, j} (\dots) = \exists x_{n} R_{i} (v_{i, 1}, \dots, v_{i, n_{i}}) \land R_{j} (v_{j, 1}, \dots, v_{j, n_{j}})

probably does not have a compact representation. Second, if we remove the quantifiers

\exists x_{n}, \exists x_{n - 1}, \dots, \exists x_{1}

one by one, potentially we could get an exponential number of relations in the formula. Let us show how these problem are solved for concrete examples on a 2-element domain.

2.9. System of linear equations in $Z_{2}$

Let

A = {0, 1}

and let

Γ

consist of linear equations in

Z_{2}

. Suppose that for every

i

we have

R_{i} (v_{i, 1}, \dots, v_{i, n_{i}}) = (a_{1}^{i} x_{n} + a_{2}^{i} x_{2} + \dots + a_{n}^{i} x_{n} = a_{0}^{i})

For

a_{n}^{i} = a_{n}^{j} = 1

, we have

\begin{aligned} R_{i, j} (\dots) \\ := \exists x_{n} (R_{i} (v_{i, 1}, \dots, v_{i, n_{i}}) \land R_{j} (v_{j, 1}, \dots, v_{j, n_{j}})) \\ = (a_{1}^{i} x_{1} + a_{2}^{i} x_{2} + \dots + a_{n - 1}^{i} x_{n - 1} + a_{0}^{i} = a_{1}^{j} x_{1} + a_{2}^{j} x_{2} + \dots + a_{n - 1}^{j} x_{n - 1} + a_{0}^{j}) \end{aligned}

a_{n}^{i} = 0

then the constraint

R_{i} (v_{i, 1}, \dots, v_{i, n_{i}})

does not depend on

x_{n}

, so we keep it as it is when remove the quantifier. Hence, in every case we have a compact representation of

Δ_{n - 1}

. To avoid the exponential growth of the number of the constraints, we use the idea from the Gaussian elimination. Choose

k

such that

a_{n}^{k} = 1

, then calculate only

R_{k, 1}, \dots, R_{k, s}

and ignore all the other relations. Thus, in this case we have

\begin{aligned} Δ_{n - 1} (x_{1}, \dots, x_{n - 1}) & = \exists x_{n} (R_{1} (v_{1, 1}, \dots, v_{1, n_{1}}) \land \dots \land R_{s} (v_{s, 1}, \dots, v_{s, n_{s}})) \\ = \underset{j \in {1, 2, \dots, s}}{⋀} (\exists x_{n} R_{k} (v_{k, 1}, \dots, v_{k, n_{k}}) \land R_{j} (v_{j, 1}, \dots, v_{j, n_{j}})) \end{aligned}

Proceeding this way, we calculate

Δ_{n - 2}, Δ_{n - 3}, \dots, Δ_{0}

. Note that (2.8) holds not only for linear equations but whenever a variable

x_{n}

is uniquely determined by the other variables in

R_{k} (v_{k, 1}, \dots, v_{k, n_{1}})

2.10. 2-satisfability

Let

A = {0, 1}

and let

Γ

consist of all binary relations. In this case

R_{i, j}

is also binary, which means that we do not have a problem with a compact representation. Also, every time we eliminate a quantifier and caclulate

Δ_{i}

, we remove the repetitive constraints. Therefore, in each

Δ_{i}

we cannot have more than

i \cdot i \cdot 2^{2^{2}}

constraints because we have

i

different variables and

2^{2^{2}}

different binary relations on

{0, 1}

As we see, the main question in both examples is the existence of a compact representation. In the first example we represent any relation as a conjunction of linear equations, in the second we represent as a conjunction of binary relations. We could ask when such a compact representation exists. Let

s_{Γ} (n)

be the number of pp-definable from

Γ

relations of arity

n

. If

\log_{2} s_{Γ} (n)

grows exponentially then we need exponential space to encode relations of arity

n

and we cannot expect a compact representation. We say that

Γ

has few subpowers if

\log_{2} s_{Γ} (n) < p (n)

for a polynomial

p (n)

. It turns out that there is a simple criterion for the constraint language to have few subpowers. An operation

t

is called an edge operation if it satisfies the following identities:

\begin{matrix} t (x, x, y, y, y, \dots, y, y) = y \\ t (x, y, x, y, y, \dots, y, y) = y \\ t (y, y, y, x, y, \dots, y, y) = y \\ t (y, y, y, y, x, \dots, y, y) = y \\ \dots \\ t (y, y, y, y, y, \dots, x, y) = y \\ t (y, y, y, y, y, \dots, y, x) = y \end{matrix}

Theorem 2.6 ([9]). A constraint language

Γ

containing all constant relations has few subpowers if and only if it has an edge polymorphism.

We can show that if

Γ

has few subpowers then the pp-definable relations have a natural compact representation, which gives a polynomial algorithm for

CSP (Г)

[33]. Note that two examples of an edge operation were given earlier in this paper. The first example is a majority operation satisfying

m (y, y, x) = m (y, x, y) = m (x, y, y) = y

. By adding 3 dummy variables in the beginning, we get the required properties of an edge operation. Another example is

x + y + z

{0, 1}

. By adding dummy variables at the end, we can easily satisfy all the identities. Very roughly speaking, any few subpowers case is just a combination (probably very complicated) of the majority case and the linear case.

2.11. Strong subuniverses and a proof of the CSP Dichotomy Conjecture

In this subsection, we consider another simple idea that can solve the CSP in polynomial time. This idea is one of the two main ingredients of the proof of the CSP Dichotomy Conjecture in

[42, 44]

Assume that for every variable

x

whose domain is

D_{x}, | D_{x} | > 1

, we can choose a subset

B_{x} ⊊ D_{x}

such that if the instance has a solution, then it has a solution with

x \in B_{x}

In this case we can reduce the domains iteratively until the moment when each domain has exactly one element, which usually gives us a solution.

As we saw in Section 2.5, if

Γ

is preserved by

x \lor y

and the instance is 1-consistent then we can safely reduce the domain of a variable to

{1}

. Similarly, if

Γ

is preserved by the majority operation

x y \lor y z \lor x z

and the instance is cycle-consistent, then we can safely reduce the domain

{0, 1}

{0}

and

{1}

[47]. It turns out that this idea can be generalized for any constraint language preserved by a WNU operation.

A unary relation

B \subseteq A

is called a subuniverse if

B

is pp-definable over

Γ

. It can be easily checked that all the domains

D_{x}

that appear while checking consistency (see Section 2.4) are subuniverses. Let us define three types of strong subuniverses:

Binary absorbing subuniverse. We say that

B^{'}

is a binary absorbing subuniverse of

B

if there exists a binary operation

f \in Pol (Γ)

such that

f (B^{'}, B) \subseteq B^{'}

and

f (B, B^{'}) \subseteq B^{'}

. For example, if the operation

x \lor y

preserves

Γ

then

{1}

is a binary absorbing subuniverse of

{0, 1}

and

x \lor y

is a binary absorbing operation.

Ternary absorbing subuniverse. We say that

B^{'}

is a ternary absorbing subuniverse of

B

if there exists a ternary operation

f \in Pol (Γ)

such that

f (B^{'}, B^{'}, B) \subseteq B^{'}, f (B^{'}, B, B^{'}) \subseteq B^{'}

, and

f (B, B^{'}, B^{'}) \subseteq B^{'}

. For example, if the majority operation

x y \lor y z \lor x z

preserves

Γ

, then both

{0}

and

{1}

are ternary absorbing subuniverses of

{0, 1}

. Since we can always add a dummy variable to a binary absorbing operation, any binary absorbing subuniverse is also a ternary absorbing subuniverse.

To define the last type of strong subalgebras we need some understanding of the Universal Algebra. We do not think a concrete definition is important here, that is why if a reader thinks the definition is too complicated, we recommend to skip it and think about the last type as something similar to the first two.

PC subuniverse. A set

F

of operations is called Polynomially Complete (PC) if any operation can be derived from

F

and constants using composition. We say that

B^{'}

is a PC subuniverse of

B

if there exists a pp-definable equivalence relation

σ \subseteq B \times B

such that

Pol (Γ) / σ

P C

A subset

B^{'}

B

is called a strong subuniverse if

B^{'}

is a ternary absorbing subuniverse or a PC subuniverse.

Theorem 2.7 ([47]). Suppose

Γ

contains all constant relations and is preserved by a WNU operation,

B \subseteq A

is a subuniverse. Then

(1) there exists a strong subuniverse

B^{'} ⊊ B

, or

(2) there exists a pp-definable nontrivial equivalence relation

σ

B

and

f \in Pol (Γ)

such that

(B; f) / σ ≅ (Z_{p}^{k}; x - y + z)

As it follows from the next lemma, the second condition implies that any ppdefinable relation (modulo

σ

) can be viewed as a system of linear equations in a field.

Lemma 2.8 ([32]). Suppose

R \subseteq Z_{p}^{n}

preserved by

x - y + z

. Then

R

can be represented as a conjunction of relations of the form

a_{1} x_{1} + \dots + a_{n} x_{n} = a_{0} (mod p)

For CSPs solvable by the local consistency checking, strong subuniverses have the following property.

Theorem 2.9 ([47]). Suppose

(1)

Γ

is a constraint language containing all constant relations;

(2)

Γ

is preserved by a

W N U

of each arity

n \geq 3

;

(3)

d

is a cycle-consistent instance of

CSP (Γ)

;

(4)

D_{x}

is the domain of a variable

x

;

(5)

B

is a strong subalgebra of

D_{x}

Then & has a solution with

x \in B

Thus, strong subuniverses have the required property that we cannot loose all the solutions when we restrict a variable to it. As it was proved in [44], a similar theorem holds for any constraint language preserved by a WNU operation (with additional consistency conditions on the instance). We skip this result because it would require too many additional definitions.

As we see from Theorem 2.7, for every domain

D_{x}

either we have a strong subuniverse and can reduce the domain of some variable, or, modulo some equivalence relation, we have a system of linear equations in a field. If

Γ

has a WNU polymorphism of each arity

n \geq 3

, then we always have the first case; hence, we can iteratively reduce the domains until the moment when all the domains have just one element, which gives us a solution. That is why any cycle-consistent instance in this situation has a solution. If we always have the second case then this situation is similar to a system of linear equations, but different linear equations can be mixed which makes it impossible to apply usual Gaussian elimination. Nevertheless, the few subpowers algorithm solves the problem [33].

For many years the main obstacle was that these two situations can be mixed and at the moment we do not know an elegant way how to split them. Nevertheless, the general algorithm for tractable CSP presented in [44] is just a smart combination of these two ideas:

if there exists a strong subalgebra, reduce
if there exists a system of linear equations, solve it.

For more information about this approach as well as its connection with the second general algorithm see

[3]

2.12. Conclusions

Even though we still do not have a simple algorithm that solves all tractable Constraint Satisfaction Problems, we understand what makes the problem hard, and what makes
the problem easy. First, we know that in all the hard cases we can pp-construct (pp-define) the not-all-equal relation, which means that all the NP-hard cases have the same nature. Second, if the CSP is not solvable locally then we can pp-construct (pp-define) a linear equation in a field. Moreover, any domain of a tractable CSP either has a strong subalgebra and we can (almost) safely reduce the domain, or there exists a system of linear equations on this domain. This implies that any tractable CSP can be solved by a smart combination of the Gaussian elimination and local consistency checking, and emphasizes the exclusive role of the linear case in Universal Algebra and Computational Complexity.

Note that both CSP algorithms in [20,44] depend exponentially on the size of the domain, and we could ask whether there exists a universal polynomial algorithm that works for any constraint language

Γ

admitting a WNU polymorphism.

Problem 1. Does there exist a polynomial algorithm for the following decision problem: given a conjunctive formula

R_{1} (v_{1, 1}, \dots, v_{1, n_{1}}) \land \dots \land R_{s} (v_{s, 1}, \dots, v_{s, n_{s}})

, where all relations

R_{1}, \dots, R_{s}

are preserved by a WNU, decide whether this formula is satisfiable.

If the domain is fixed then the above problem can be solved by the algorithms from [19,42]. In fact, we know from [4, THEOREM 4.2] that from a WNU on a domain of size

k

we can always derive a WNU (and also a cyclic operation) of any prime arity greater than

k

. Thus, we can find finitely many WNU operations on a domain of size

k

such that any constraint language preserved by a WNU is preserved by one of them. It remains to apply the algorithm for each WNU and return a solution if one of them gave a solution.

3. QUANTIFIED CSP

A natural generalization of the CSP is the Quantified Constraint Satisfaction Problem (QCSP), where we allow to use both existential and universal quantifiers. Formally, for a constraint language

Γ, QCSP (Γ)

is the problem to evaluate a sentence of the form

\forall x_{1} \exists y_{1} \dots \forall x_{n} \exists y_{n} R_{1} (v_{1, 1}, \dots, v_{1, n_{1}}) \land \dots \land R_{s} (v_{s, 1}, \dots, v_{s, n_{s}})

where

R_{1}, \dots, R_{s} \in Γ

, and

v_{i, j} \in {x_{1}, \dots, x_{n}, y_{1}, \dots, y_{n}}

for every

i, j

(see

[16, 23, 24, 37]

). Unlike the

CSP

, the problem

QCSP (Γ)

can be PSpace-hard if the constraint language

Γ

is powerful enough. For example,

QCSP ({N A E})

and

Q C S P ({1 I N 3})

on the domain

A = {0, 1}

are PSpace-hard [25,27], and

QCSP ({\neq})

for

| A | > 2

is also PSpace-hard [16]. Nevertheless, if

Γ

consists of linear equations modulo

p

then

QCSP (Γ)

is tractable [16]. It was conjectured by Hubie Chen

[22, 24]

that for any constraint language

Γ

the problem QCSP

(Γ)

is either solvable in polynomial time, or NP-complete, or PSpace-complete. Recently, this conjecture was disproved in [48], where the authors found constraint languages

Γ

such that

QCSP (Γ)

is coNPcomplete (on a 3-element domain), DP-complete (on a 4-element domain),

Θ_{2}^{P}

-complete (on a 10-element domain). Despite the whole zoo of the complexity classes, we still hope to obtain a full classification of the complexity for each constraint language

Γ

Below we consider the main idea that makes the problem easier than PSpace.

3.1. PGP reduction for $Π_{2}$ restrictions

For simplicity let us consider the

Π_{2}

-restriction of

QCSP (Γ)

, denoted

{QCSP}^{2} (Γ)

, in which the input is of the form

\begin{matrix} (3.1) & \forall x_{1} \dots \forall x_{n} \exists y_{1} \dots \exists y_{m} R_{1} (\dots) \land \dots \land R_{s} (\dots) \end{matrix}

Such an instance holds whenever the conjunctive formula

R_{1} (\dots) \land \dots \land R_{S} (\dots)

is solvable for any evaluation of

x_{1}, \dots, x_{n}

, which gives us a reduction of the instance to

| A |^{n}

instances of

CSP (Γ^{*})

, where by

Γ^{*}

we denote

Γ \cup {(x = a) ∣ a \in A}

. If we need to check

| A |^{n}

tuples, which is exponentially many, this does not make the problem easier. Nevertheless, sometimes it is sufficient to check only polynomially many tuples. Let us consider a concrete example.

System of linear equations. Suppose

A = {0, 1}

and

Γ

consists of linear equations in

Z_{2}

. Let us check that the instance (3.1) holds for

(x_{1}, \dots, x_{n}) = (0, \dots, 0)

, and

(x_{1}, \dots, x_{n}) =

(0, \dots, 0, 1, 0, \dots, 0)

for any position of 1 . To do this, we solve the CSP instance

R_{1} (\dots) \land

\dots \land R_{s} (\dots) \land ⋀_{i = 1}^{n} (x_{i} = 0)

, and for every

j \in {1, 2, \dots, n}

we solve the instance

R_{1} (\dots) \land \dots \land R_{s} (\dots) \land (x_{j} = 1) \land \underset{i \neq j}{⋀} (x_{i} = 0)

. Each instance is a system of linear equations and can be solved in polynomial time. If at least one of the instances does not have a solution, then the instance (3.1) does not hold. Assume that all of them are satisfiable, then consider the relation

Δ

defined by the following pp-formula over

Γ

Δ (x_{1}, \dots, x_{n}) = \exists y_{1} \dots \exists y_{m} R_{1} (\dots) \land \dots \land R_{s} (\dots)

Since

Γ

is preserved by

x + y + z, Δ

is also preserved by

x + y + z

. Applying this operation to the tuples

(0, 0, \dots, 0), (1, 0, \dots, 0), (0, 1, 0, \dots, 0), \dots, (0, 0, \dots, 0, 1) \in Δ

coordinatewise, we derive that

Δ = {0, 1}^{n}

, that is,

Δ

contains all tuples and (3.1) holds. Thus, we showed that

{QCSP}^{2} (Γ)

is solvable in polynomial time.

This idea can be generalized as follows. We say that a set of operations

F

(or an algebra

(A; F))

has the polynomially generated powers (PGP) property if there exists a polynomial

p (n)

such that

A^{n}

can be generated from

p (n)

tuples using operations of

F

. Another behavior that might arise is that there is an exponential function

f

so that the smallest generating sets for

A^{n}

require size at least

f (n)

. We describe this as the exponentially generated powers (EGP) property. As it was proved in [43] these are the only two situations we could have on a finite domain. Moreover, it was shown that the generating set in the PGP case can be chosen to be very simple and efficiently computable. As a generating set of polynomial size, we can take the set of all tuples with at most

k

switches, where a switch is a position in

(a_{1}, \dots, a_{n})

such that

a_{i} \neq a_{i + 1}

. This gives a polynomial reduction of

{QCSP}^{2} (Γ)

CSP (Γ^{*})

Pol (Γ)

has the

P G P

property.

3.2. A general PGP reduction

Let us show that the same idea can be applied to the general form of

QCSP (Γ)

. First, we show how to move universal quantifiers left and convert an instance into the

Π_{2}

-form. Notice that the sentence

\exists y_{1} \exists y_{2} \dots \exists y_{s} \forall x Φ

is equivalent to

\forall x^{1} \forall x^{2} \dots \forall x^{| A |} \exists y_{1} \exists y_{2} \dots \exists y_{s} Φ_{1} \land Φ_{2} \land \dots \land Φ_{| A |}

where each

Φ_{i}

is obtained from

Φ

by renaming

x

x^{i}

. In this way we can convert any instance

\exists y_{1} \forall x_{1} \dots \exists y_{t} \forall x_{t} Φ

QCSP (Γ)

into the

Π_{2}

-restriction by moving all universal quantifiers left:

\begin{aligned} \forall x_{1}^{1} \dots \forall x_{1}^{| A |} \forall x_{2}^{1} \dots \forall x_{2}^{| A |^{2}} \dots \forall x_{t}^{1} \dots \forall x_{t}^{| A |^{t}} \\ (3.2) & \exists y_{1} \exists y_{2}^{1} \dots \exists y_{2}^{| A |} \dots \exists y_{t}^{1} \dots \exists y_{t}^{| A |^{t - 1}} Φ_{1} \land Φ_{2} \land \dots \land Φ_{q} \end{aligned}

where each

Φ_{i}

is obtained from

Φ

by renaming the variables. The only problem with this reduction is that the number of variables and constraints could be exponential. Nevertheless, we can apply the PGP idea to this sentence. If

Pol (Γ)

has the PGP property then there exists a constant

k

such that it is sufficient to check (3.2) only on the tuples with at most

k

switches. Those

k

switches appear in at most

k

original

x

-variables and all the remaining variables can be fixed with constants. This allows reducing

QCSP (Γ)

to a sentence with a constant number of universal quantifiers or even remove all of them.

Theorem 3.1 ([45]). Suppose

Pol (Γ)

has the PGP property. Then

QCSP (Γ)

is polynomially equivalent to the modification of

{QCSP}^{2} (Γ)

where sentences have at most

| A |

universally quantified variables.

Theorem 3.2 ([45]). Suppose

Pol (Γ)

has the

P G P

property. Then

QCSP (Γ)

is polynomially reduced to

CSP (Γ^{*})

This idea gives us a complete classification of the complexity of

QCSP (Γ)

for a two-element domain.

Theorem 3.3 ([25, 27]). Suppose

Γ

is a constraint language on

{0, 1}

. Then

QCSP (Γ)

is solvable in polynomial time if

Γ

is preserved by an idempotent WNU;

QCSP (Γ)

is PSpacecomplete otherwise.

It is known [39] that if

Γ

admits an idempotent WNU, then it is preserved by

x + y + z, x \lor y, x \land y

, or

x y \lor y z \lor x z

. Hence, to prove the above theorem, it is sufficient to check that these operations guarantee the PGP property, which by Theorem 3.2 gives a polynomial reduction to a tractable CSP. To show the PGP property, we verify that the tuples

(0, 0, \dots, 0), (1, 1, \dots, 1), (1, 0, \dots, 0), (0, 1, 0, \dots, 0), \dots, (0, \dots, 0, 1)

generate

{0, 1}^{n}

using any of the above operations.

3.3. Does EGP mean hard?

Thus, if

Pol (Γ)

has the PGP property then we have a nice reduction to CSP, and

QCSP (Γ)

belongs to NP. What can we say about the complexity of

QCSP (Γ)

Pol (Γ)

has the EGP property? Hubie Chen conjectured in [24] that

Q C S P (Γ)

is PSpace-complete whenever

Pol (Γ)

has the EGP property.

For constraint languages

Γ

containing all constant relations, a characterization of

Pol (Γ)

that have the EGP property is given in [43], where it is shown that

Γ

must allow the pp-definition of relations

τ_{n}

with the following special form.

Definition 3.4. Let

α \cup β = A

, yet neither

α

nor

β

equals

D

. Let

S = α^{3} \cup β^{3}

and

τ_{n}

be the

3 n

-ary relation given by

⋁_{i = 1}^{n} S (x_{i}, y_{i}, z_{i})

The complement to

S

represents the not-all-equal relation and the relations

τ_{n}

allow for the encoding of the complement of Not-All-Equal 3-Satisfiability (where

α ∖ β

is 0 and

β ∖ α

is 1). Thus, if one has polynomially computable (in

n

) pp-definitions of

τ_{n}

, then it is clear that

QCSP (Γ)

is co-NP-hard [22]. In light of this observation, it seemed that only a small step remained to proving the actual Chen Conjecture, at least with coNP-hard in place of PSpace-complete.

3.4. Surprising constraint language and the QCSP on a 3-element domain

As we saw in Section 2.7, the CSP is NP-hard if and only the we can pp-define (pp-construct) the not-all-equal relation. In the previous subsection, we mentioned that in the EGP case we can always pp-construct the complement to Not-All-Equal 3-Satisfability, which almost guarantees coNP-hardness. Surprisingly, two constraint languages

Γ

A = {0, 1, 2}

were discovered in [48] for which any pp-definition of

τ_{n}

is of exponential size, which makes it impossible to use this reduction.

Theorem 3.5 ([48]). There exists a constraint language

Γ

{0, 1, 2}

such that

(1)

Pol (Γ)

has the EGP property,

(2)

τ_{n}

is pp-definable over

Γ

(3) any pp-definition of

τ_{n}

for

α = {0, 1}

and

β = {0, 2}

has at least

2^{n}

variables, and

(4)

QCSP (Γ)

is solvable in polynomial time.

The algorithm in (4) consists of the following three steps. First, it reduces an instance to a

Π_{2}

-form

\forall x_{1} \dots \forall x_{n} \exists y_{1} \dots \exists y_{m} Φ

. Then, by solving polynomially many CSPs, it calculates polynomially many evaluations to

(x_{1}, \dots, x_{n})

we need to check. Finally, it checks that

Φ

has a solution for each of these evaluations. It is proved in [48] that this test guarantees that the instance holds.

This result was shocking because of several reasons. Not only it disproved the widely believed Chen Conjecture but showed that we need to worry about the existence of an efficient pp-definition. Before, if we could pp-define a strong relation (such as

τ_{n}

) then the problem was hard. Another surprising thing is that we have to calculate the evaluations of

(x_{1}, \dots, x_{n})

we need to check, In fact, if we do not look inside

Φ

then we have to check all the tuples from

{0, 1}^{n}

Despite the fact that we are far from having a full classification of the complexity of the QCSP, we know the complexity for any constraint language on a 3-element domain containing all constant relations. This classification is given in terms of polymorphisms.

Theorem 3.6 ([48]). Suppose

Γ

is a finite constraint language on

{0, 1, 2}

containing all constant relations. Then

Q C S P (Γ)

is either solvable in polynomial time,

N P

-complete, coNPcomplete, or PSpace-complete.

3.5. Conclusions

Unlike the CSP where the complexity is known for any constraint language

Γ

here the complexity is wide open.

Problem 2. What is the complexity of

QCSP (Γ)

Moreover, we do not even have a conjecture describing the complexity. We know that for some constraint languages

Γ

the problem

QCSP (Γ)

is DP-complete and

Θ_{2}^{P}

-complete, but we do not know whether there are some other complexity classes and whether we have finitely many of them.

Problem 3. What complexity classes (up to polynomial equivalence) can be expressed as

QCSP (Γ)

for some constraint language

Γ

Now it is hard to believe that there will be a simple classification, that is why it is interesting to start with a 3-element domain (without constant relations) and 4-element domain. Probably, a more important problem is to describe all tractable cases assuming

P \neq N P

Problem 4. Describe all constraint languages

Γ

such that

QCSP (Γ)

is solvable in polynomial time.

4. OTHER VARIANTS OF CSP

The Quantified CSP is only one of many other variations and generalizations of the CSP whose complexity is still unknown. Here we list some of them.

4.1. CSP over an infinite domain

If we consider

CSP (Γ)

for a constraint language on an infinite domain, the situation changes significantly. As was shown in [11], every computational problem is equivalent (under polynomial-time Turing reductions) to a problem of the form

CSP (Γ)

. In [14] the authors gave a nice example of a constraint language

Γ

such that

CSP (Γ)

is undecidable. Let

Γ

consist of three relations (predicates)

x + y = z, x \cdot y = z

and

x = 1

over the set of all integers

Z

. Then the Hilbert's 10th problem can be expressed as

CSP (Γ)

, which proves undecidability of

CSP (Γ)

. Nevertheless, there are additional assumptions that send the CSP back to the class NP and make complexity classifications possible [8,12]. For more information about the infinite domain CSP and the algebraic approach, see [10,14].

4.2. Surjective Constraint Satisfaction Problem

A natural modification of the CSP is the Surjective Constraint Satisfaction Problem, where we want to find a surjective solution. Formally, for a constraint language

Γ

over a domain

A, SCSP (Γ)

is the following decision problem: given a formula

R_{1} (\dots) \land \dots \land R_{s} (\dots)

where all relations

R_{1}, \dots, R_{s}

are from

Γ

, decide whether there exists a surjective solution, that is, a solution with

{x_{1}, \dots, x_{n}} = A

. Probably, the most natural examples of the Surjective CSP are defined as the surjective graph homomorphism problem, which is equivalent to

SCSP (Γ)

where

Γ

consists of one binary relation that is viewed as a graph. An interesting fact about the complexity of the Surjective CSP is that its complexity remained unknown for many years even for very simple graphs and constraint languages. Three most popular examples of such long-standing problems are the complexity for the reflexive 4-cycle (undirected having a loop at each vertex) [38], the complexity for the nonreflexive 6-cycle (undirected without loops) [41], and the complexity of the No-Rainbow-Problem

(SCSP ({N})

where

A = {0, 1, 2}

and

N = {(a, b, c) ∣ {a, b, c} \neq A})

[46]. Even though these three problems turned out to be NP-complete, the complexity seems to be unknown even for graphs of size 5 and cycles.

Problem 5. What is the complexity of

SCSP (Γ)

It was shown in [46] that the complexity of

SCSP (Γ)

cannot be described in terms of polymorphisms, which disproved the only conjecture about the complexity of

SCSP (Γ)

we know. This conjecture, formulated by Hubie Chen, says that

SCSP (Γ)

and

CSP (Γ^{*})

have the same complexity. Nevertheless, this conjecture still can hold for graphs.

Problem 6. Is it true that

SCSP ({R})

and

CSP ({R}^{*})

have the same complexity for any binary relation

R

For more results on the complexity of the SCSP, see the survey [13].

4.3. Promise CSP

A natural generalization of the CSP is the Promise Constraint Satisfaction Problem, where a promise about the input is given (see [18,21]). Let

Γ = {(R_{1}^{A}, R_{1}^{B}), \dots, (R_{t}^{A}, R_{t}^{B})}

, where

R_{i}^{A}

and

R_{i}^{B}

are relations of the same arity over the domains

A

and

B

, respectively. Then

PCSP (Γ)

is the following decision problem: given two conjunctive formulas

\begin{aligned} R_{i_{1}}^{A} (v_{1, 1}, \dots, v_{1, n_{1}}) \land \dots \land R_{i_{s}}^{A} (v_{s, 1}, \dots, v_{s, n_{s}}) \\ R_{i_{1}}^{B} (v_{1, 1}, \dots, v_{1, n_{1}}) \land \dots \land R_{i_{s}}^{B} (v_{s, 1}, \dots, v_{s, n_{s}}) \end{aligned}

where

(R_{i_{j}}^{A}, R_{i_{j}}^{B})

are from

Γ

for every

j

and

v_{i, j} \in {x_{1}, \dots, x_{n}}

for every

i, j

, distinguish between the case when both of them are satisfiable, and when both of them are not satisfiable. Thus, we are given two CSP instances and a promise that if one has a solution then another has a solution. Usually, it is also assumed that there exists a mapping (homomorphism)

h : A \to B

such that

h (R_{i}^{A}) \subseteq R_{i}^{B}

for every

i

. In this case, the satisfiability of the first formula implies
the satisfiability of the second one. To make sure that the promise can actually make an NP-hard problem tractable, see Example 2.8 in [21].

The most popular example of the Promise CSP is graph

(k, l)

-colorability, where we need to distinguish between

k

-colorable graphs and not even

l

-colorable, where

k \leq l

. This problem can be written as follows.

Problem 7. Let

| A | = k, | B | = l, Γ = {(\neq_{A}, \neq_{B})}

. What is the complexity of

PCSP (Γ)

Recently, it was proved [21] that

(k, l)

-colorability is NP-hard for

l = 2 k - 1

and

k \geq 3

but even the complexity of

(3, 6)

-colorability is still not known.

Even for a 2-element domain the problem is wide open, but recently a dichotomy for symmetric Boolean PCSP was proved [30].

Problem 8. Let

A = B = {0, 1}

. What is the complexity of

PCSP (Γ)

REFERENCES

[1] S. Arora and B. Barak, Computational complexity: a modern approach. Cambridge University Press, 2009.

[2] K. A. Baker and F. Pixley, Polynomial interpolation and the Chinese Remainder Theorem for algebraic systems. Math. Z. 143 (1975), 165-174.

[3] L. Barto, Z. Brady, A. Bulatov, M. Kozik, and D. Zhuk, Minimal Taylor algebras as a common framework for the three algebraic approaches to the CSP In 2021 36th annual ACM/IEEE symposium on logic in computer science (LICS), pp. 1-13, IEEE, 2021.

[4] L. Barto and M. Kozik, Absorbing subalgebras, cyclic terms, and the Constraint Satisfaction Problem. Log. Methods Comput. Sci. 8 (2012), no. 1.

[5] L. Barto and M. Kozik, Constraint satisfaction problems solvable by local consistency methods. J. ACM 61 (2014), no. 1, 1-19.

[6] L. Barto, A. Krokhin, and R. Willard, Polymorphisms, and how to use them.

Dagstuhl Follow-Ups 7, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017.

[7] L. Barto, J. OprÅ¡al, and M. Pinsker, The wonderland of reflections. Israel J. Math. 223 (2018), no. 1, 363-398.

[8] L. Barto and M. Pinsker, The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems. In 2016 31st annual ACM/IEEE symposium on logic in computer science (LICS), pp. 1-8, IEEE, 2016.

[9] J. Berman, P. Idziak, P. MarkoviÄ‡, R. McKenzie, M. Valeriote, and R. Willard, Varieties with few subalgebras of powers. Trans. Amer. Math. Soc. 362 (2010), no. 3, 1445-1473.

[10] M. Bodirsky, Complexity classification in infinite-domain constraint satisfaction. 2012, arXiv:1201.0856.

[11] M. Bodirsky and M. Grohe, Non-dichotomies in constraint satisfaction complexity. In International colloquium on automata, languages, and programming, pp. 184-196, Springer, 2008.

[12] M. Bodirsky and J. KÃ¡ra, The complexity of temporal constraint satisfaction problems. J. ACM 57 (2010), no. 2, 9.

[13] M. Bodirsky, J. KÃ¡ra, and B. Martin, The complexity of surjective homomorphism problems - a survey. Discrete Appl. Math. 160 (2012), no. 12, 1680-1690.

[14] M. Bodirsky and M. Mamino, Constraint satisfaction problems over numeric domains. Dagstuhl Follow-Ups 7, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017.

[15] V. G. Bodnarchuk, L. A. Kaluzhnin, V. N. Kotov, and B. A. Romov, Galois theory for post algebras parts I and II. Cybernetics 5 (1969), 243-252, 531-539. 9

[16] F. BÃ¶rner, A. A. Bulatov, H. Chen, P. Jeavons, and A. A. Krokhin, The complexity of constraint satisfaction games and QCSP. Inform. and Comput. 207 (2009), no. 9, 923-944.

[17] J. Brakensiek, S. Gopi, and V. Guruswami, CSPs with global modular constraints: algorithms and hardness via polynomial representations. In Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, pp. 590-601, Association for Computing Machinery, 2019.

[18] J. Brakensiek and V. Guruswami, Promise constraint satisfaction: structure theory and a symmetric boolean dichotomy. In Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms, pp. 1782-1801, SIAM, 2018.

[19] A. A. Bulatov, A dichotomy theorem for nonuniform CSPs. In 2017 IEEE 58th annual symposium on foundations of computer science (FOCS), pp. 319-330, IEEE, 2017.

[20] A. A. Bulatov, A dichotomy theorem for nonuniform CSPs. 2017, arXiv:1703.03021.

[21] J. BulÃn, A. Krokhin, and J. OprÅ¡al, Algebraic approach to promise constraint satisfaction. In Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, pp. 602-613, ACM, 2019.

[22] C. Carvalho, B. Martin, and D. Zhuk, The complexity of quantified constraints using the algebraic formulation. In 42nd international symposium on mathematical foundations of computer science, MFCS 2017, August 21-25, 2017 Aalborg, Denmark, pp. 27:1-27:14, Leibniz Center for Informatics, 2017.

[23] H. Chen, The complexity of quantified constraint satisfaction: Collapsibility, sink algebras, and the three-element case. SIAM J. Comput. 37 (2008), no. 5,

1674 - 1701

[24] H. Chen, Meditations on quantified constraint satisfaction. In Logic and program semantics - essays dedicated to Dexter Kozen on the occasion of his 60th birthday, pp. 35-49, Springer, 2012.

[25] N. Creignou, S. Khanna, and M. Sudan, Complexity classifications of boolean constraint satisfaction problems. SIAM, 2001.

[26] N. Creignou, H. Schnoor, and I. Schnoor, Non-uniform boolean constraint satisfaction problems with cardinality constraint. In International workshop on computer science logic, pp. 109-123, Springer, 2008.

[27] V. Dalmau, Some dichotomy theorems on constant-free quantified boolean formulas Tech. rep. LSI97-43-R. Llenguatges i Sistemes InformÃ¡tics-Universitat PolitÃ©cnica de Catalunya, Barcelona, Spain, 1997.

[28] T. Feder and M. Y. Vardi, Monotone monadic SNP and constraint satisfaction. In Proceedings of the twenty-fifth annual ACM symposium on theory of computing, pp. 612-622, Association for Computing Machinery, 1993.

[29] T. Feder and M. Y. Vardi, The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory. SIAM J. Comput. 28 (1999), no. 1, 57-104.

[30] M. Ficak, M. Kozik, M. Olsak, and S. Stankiewicz, Dichotomy for symmetric boolean PCSPs. 2019, arXiv:1904.12424.

[31] D. Geiger, Closed systems of functions and predicates. Pacific J. Math. 27 (1968), no.

1, 95 - 100

[32] W. H. Greub, Linear algebra. Grad. Texts in Math. 23, Springer, 2012.

[33] P. Idziak, P. MarkoviÄ‡, R. McKenzie, M. Valeriote, and R. Willard, Tractability and learnability arising from algebras with few subpowers. SIAM J. Comput. 39 (2010), no. 7, 3023-3037.

[34] P. Jeavons, On the algebraic structure of combinatorial problems. Theoret. Comput. Sci. 200 (1998), no. 1-2, 185-204.

[35] P. Jeavons, D. Cohen, and M. C. Cooper, Constraints, consistency and closure. Artif. Intell. 101 (1998), no. 1-2, 251-265.

[36] M. Kozik, Weak consistency notions for all the CSPs of bounded width. In 2016 31st annual ACM/IEEE symposium on logic in computer science (LICS), pp. 1-9, IEEE, 2016.

[37] B. Martin, Quantified Constraints in Twenty Seventeen. In The constraint satisfaction problem: complexity and approximability, edited by A. Krokhin and S. Zivny, pp. 327-346, Dagstuhl Follow-Ups 7, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017.

[38] B. Martin and D. Paulusma, The computational complexity of disconnected cut and 2 k2-partition. J. Combin. Theory Ser. B 111 (2015), 17-37.

[39] E. L. Post, The two-valued iterative systems of mathematical logic. Ann. of Math. Stud. 5, Princeton University Press, Princeton, NJ, 1941.

[40] T. J. Schaefer, The complexity of satisfiability problems. In Proceedings of the tenth annual ACM symposium on theory of computing, STOC'78, pp. 216-226, ACM, New York, NY, USA, 1978.

[41] N. Vikas, Computational complexity of graph partition under vertex-compaction to an irreflexive hexagon. In 42nd international symposium on mathematical foundations of computer science, MFCS 2017, pp. 69:1-69:14, LIPIcs 83, Leibniz Center for Informatics, 2017.

[42] D. Zhuk, A proof of CSP dichotomy conjecture. In 2017 IEEE 58th annual symposium on foundations of computer science (FOCS), pp. 331-342, IEEE, 2017.

[43] D. Zhuk, The size of generating sets of powers. J. Combin. Theory Ser. A 167 (2019), 91-103.

[44] D. Zhuk, A proof of the CSP dichotomy conjecture. J. ACM 67 (2020), no. 5,

1 - 78

[45] D. Zhuk, The complexity of the Quantified CSP having the polynomially generated powers property. 2021, arXiv:2110.09504.

[46] D. Zhuk, No-rainbow problem and the surjective constraint satisfaction problem. In 2021 36th annual ACM/IEEE symposium on logic in computer science (LICS), pp. 1-7, IEEE, 2021.

[47] D. Zhuk, Strong subalgebras and the constraint satisfaction problem. J. Mult.Valued Logic Soft Comput. 36 (2021).

[48] D. Zhuk and B. Martin, QCSP monsters and the demise of the Chen conjecture. In Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, pp. 91-104, 2020.

DMITRIY ZHUK

Department of Mechanics and Mathematics, Lomonosov Moscow State University, Vorobjovy Gory, 119899 Moscow, Russia, zhuk @intsys.msu.ru

ALGEBRA

A TOTALLY DISCONNECTED INVITATION TO LOCALLY COMPACT GROUPS

PIERRE-EMMANUEL CAPRACE ANDGEORGE A. WILLIS

ABSTRACT

We present a selection of results contributing to a structure theory of totally disconnected locally compact groups.

MATHEMATICS SUBJECT CLASSIFICATION 2020

Primary 22D05; Secondary 20E15, 20E32, 20E08, 22F50, 43A07

KEYWORDS

Locally compact group, profinite group, amenable group, simple group, topological dynamics, commensurated subgroup, minimising subgroup, flat group of automorphisms

1. INTRODUCTION

Locally compact groups have attracted sustained attention because, on the one hand, rich classes of these groups have fruitful connections with other fields and, on the other, they have a well-developed theory that underpins those connections and delineates group structure. Salient features of this theory are the existence of a left-invariant, or Haar, measure; and the decomposition of a general group into pieces, many of which may be described concretely and in detail.

Haar measure permits representations of a general locally compact group by operators on spaces of measurable functions, and is thus the foundation for abstract harmonic analysis. Connections with partial differential equations, physics, and number theory come about through these representations. Locally compact groups are the largest class for which an invariant measure exists and for which harmonic analysis can be done in this form, as was shown by A. Weil [81].

The decomposition theory of an arbitrary locally compact group

G

begins with the short exact sequence

0 \to G^{\circ} \to G \to G / G^{\circ} \to 0

in which the closed normal subgroup

G^{\circ}

is the connected component of the identity. The Gleason-Yamabe theorem [73, Ñ‚Ð½. 6.0.11] applies to

G^{\circ}

to show that it is a projective limit of connected Lie groups, and powerful tools from the theory of Lie groups may thus be brought to bear on

G^{\circ}

. Groups occurring in physics and differential equations are often Lie groups. The quotient

G / G^{\circ}

is a totally disconnected locally compact group (abbreviated tdlc group). Lie groups over local fields are important examples of tdlc groups having links to number theory and algebraic geometry (see, for example,

[49, 69]

). Unlike the connected case however, many other significant tdlc groups, such as the automorphism groups of locally finite trees first studied in [76], cannot be approximated by Lie groups. While substantial progress has been made with our understanding of tdlc groups much remains to be done before it could be said that the structure theory has reached maturity. This article surveys our current state of knowledge, much of which is founded on a theorem of van Dantzig, [77], which ensures that a tdlc group

G

has a basis of identity neighborhoods consisting of compact open subgroups.

Decompositions of general tdlc groups are described in Section 2. This section includes a discussion of the so-called elementary groups, which are those built from discrete and compact groups by standard operations. Discrete and compact groups are large domains of study in their own right and it is seen how elementary groups can be factored out in the analysis of a general tdlc group. Simple groups are an important aspect of any decomposition theory and what is known about them is summarized in Section 3. This includes a local structure theory and the extent to which local structure determines the global structure of the group. Section 4 treats scale methods, which associate invariants and special subgroups to abelian groups of automorphisms and which in some circumstances substitute for the Lie methods available for connected groups. A unifying theme of our approach is the dynamics of the conjugation action: Section 2 is concerned with the conjugation action of

G

on its closed subnormal subgroups, Section 3 uses in an essential way the conjugation
action of

G

on its closed subgroups, especially those that are locally normal, while Section 4 concerns the dynamics of the conjugation action of cyclic subgroups (and, more generally, flat subgroups) on the topological space

G

. Section 5 highlights a few open questions and directions for further research.

2. DECOMPOSITION THEORY

2.1. Normal subgroup structure

Finite groups, Lie groups, and algebraic groups constitute three of the most important classes of groups. Their respective structure theories are deep and far-reaching. One of the common themes consists in reducing problems concerning a given group

G

in one of these classes to problems about simple groups in the corresponding class, and then tackling the reduced problem by invoking classification results. Striking illustrations of this approach in the case of finite groups can be consulted in R. Guralnick's ICM address [43].

Since the category of locally compact groups contains all discrete groups, hence all groups, developing a similar theory for locally compact groups is hopeless. Nevertheless, the possibility to construct meaningful "decompositions of locally compact groups into simple pieces" has been highlighted in [23]. Wide-ranging results have subsequently been established by C. Reid and P. Wesolek in a series of papers [63,64], some of whose contributions are summarized below. A more in-depth survey can be consulted in [62].

Given closed normal subgroups

K, L

of a locally compact group

G

, the quotient group

K / L

is called a chief factor of

G

L

is strictly contained in

K

and for every closed normal subgroup

N

G

with

L \leq N \leq K

, we have

N = L

N = K

. Given a closed normal subgroup

N

G

, the quotient

Q = G / N

is a chief factor if and only if

Q

is topologically simple, i.e.,

Q

is nontrivial and the only closed normal subgroups of

Q

are

{1}

and

Q

. More generally, every chief factor

Q = K / L

is topologically characteristically simple, i.e., the only closed subgroups of

Q

that are invariant under all homeomorphic automorphisms of

Q

are

{1}

and

Q

. A topological group is called compactly generated if it has a compact generating set.

Theorem 2.1 (See [64, Ñ‚Ð½. 1.3]). Every compactly generated tdlc group

G

has a finite series

{1} = G_{0} < G_{1} < G_{2} < \dots < G_{n} = G

of closed normal subgroups such that for all

i = 1, \dots, n

, the quotient

G_{i} / G_{i - 1}

is compact, or discrete infinite, or a chief factor of

G

which is noncompact, nondiscrete, and second countable.

A normal series as in Theorem 2.1 is called an essentially chief series. The theorem obviously has no content if

G

is compact or discrete. Let us illustrate Theorem 2.1 with two examples.

Example 2.2. Let

I

be a set and for each

i \in I

, let

G_{i}

be a tdlc group and

U_{i} \leq G_{i}

be a compact open subgroup. The restricted product of

{(G_{i}, U_{i})}_{i \in I}

, denoted by

⨁_{i \in I} (G_{i}, U_{i})

, is the subgroup of

\prod_{i \in I} G_{i}

consisting of those tuples

{(g_{i})}_{i \in I}

such that

g_{i} \in U_{i}

for all but finitely many

i \in I

. It is endowed with the unique tdlc group topology such that
the inclusion

\prod_{i \in I} U_{i} \to ⨁_{i \in I} (G_{i}, U_{i})

is continuous and open. Given a prime

p

, set

M (p) = ⨁_{n \in Z} ({P S L}_{2} (Q_{p}), {P S L}_{2} (Z_{p}))

. The cyclic group

Z

naturally acts on

M (p)

by shifting the coordinates. The semidirect product

G (p) = M (p) ⋊ Z

is a compactly generated tdlc group, with an essentially chief series given by

{1} < M (p) < G (p)

. The group

M (p)

is not compactly generated. It has minimal closed normal subgroups, but does not admit any finite essentially chief series, which illustrates the necessity of the compact generation hypothesis in Theorem 2.1.

Example 2.3. A more elaborate construction in [63, Â§9] yields an example of a compactly generated tdlc group

G^{'} (p)

with an essentially chief series given by

{1} < H (p) < G^{'} (p)

such that

G^{'} (p) / H (p) ≅ Z

and

H (p)

has a nested chain of closed normal subgroups

(H (p)_{n})

indexed by

Z

, permuted transitively by the conjugation

G^{'} (p)

-action, and such that

H (p)_{n} / H (p)_{n - 1} ≅ M (p)

for all

n \in Z

A tdlc group is compactly generated if and only if it is capable of acting continuously, properly, with finitely many vertex orbits, by automorphisms on a connected locally finite graph. For a given compactly generated tdlc group

G

, vertex-transitive actions on graphs are afforded by the following construction. Given a compact open subgroup

U < G

, guaranteed to exist by van Dantzig's theorem, and a symmetric compact generating set

Σ

G

, we construct a graph

Γ

whose vertex set is the coset space

G / U

by declaring that the vertices

g U

and

h U

are adjacent if

h^{- 1} g

belongs to

U Σ U

. The fact that

Σ

generates

G

ensures that

Γ

is connected. Moreover,

G

acts vertex-transitively by automorphisms on

Γ

. Since

U

is compact open, the set

U Σ U

is a finite union of double cosets modulo

U

; this implies that

Γ

is locally finite, i.e., the degree of each vertex is finite. Notice that all vertices have the same degree since

Γ

is homogeneous. The graph

Γ

is called a Cayley-Abels graph for

G

, since its construction was first envisaged by H. Abels [1, BEISPIEL 5.2] and specializes to a Cayley graph when

G

is discrete and

U = {1}

. The proof of Theorem 2.1 proceeds by induction on the minimum degree of a Cayley-Abels graph.

2.2. Elementary groups

By its very nature, Theorem 2.1 highlights the special role played by compact and discrete groups. A conceptual approach to studying the role of compact and discrete groups in the structure theory of tdlc groups is provided by P. Wesolek's notion of elementary groups. That concept is inspired by the class of elementary amenable discrete groups introduced by M. Day [33]. It is defined as the smallest class

E

of second countable tdlc groups (abbreviated tdlcsc) containing all countable discrete groups and all compact tdlcsc groups, which is stable under the following two group theoretic operations:

Given a tdlcsc group $G$ and a closed normal subgroup $N$ , if $N \in E$ and $G / N \in E$ , then $G \in E$ . In other words $E$ is stable under group extensions.
Given a tdlcsc group $G$ and a directed set ${(O_{i})}_{i \in I}$ of open subgroups, if $O_{i} \in E$ for all $i$ and if $G = ⋃_{i} O_{i}$ , then $G \in E$ . In other words $E$ is stable under directed unions of open subgroups.

(The class

E

has a natural extension beyond the second countable case, see [29, $6]. For simplicity of the exposition, we stick to the second countable case here.) Using the permanence properties of the class

E

, it can be shown that every tdlcsc group

G

has a largest closed normal subgroup that is elementary; it is denoted by

R_{E} (G)

and called the elementary radical of

G

. It indeed behaves as a radical, in the sense that it contains all elementary closed normal subgroups, and satisfies

R_{E} (G / R_{E} (G)) = {1}

, see [82, 87.2]. Further properties of the quotient

G / R_{E} (G)

will be mentioned in Section 3 below.

Similarly as for elementary amenable discrete groups, the class

E

admits a canonical rank function

ξ : E \to ω_{1}

, taking values in the set

ω_{1}

of countable ordinals, called the decomposition rank. It measures the complexity of a given group

G \in E

. By convention, the function

ξ

is extended to all tdlcsc groups by setting

ξ (G) = ω_{1}

for each nonelementary tdlcsc group

G

. We refer to [82], [83] and [62, $5]. Let us merely mention here that the class

E

has remarkable permanence properties (e.g., it is stable under passing to closed subgroups and quotient groups), that the rank function has natural monotonicity properties, and that a nontrivial compactly generated group

G \in E

has a nontrivial discrete quotient. It follows in particular that if

G

is a tdlcsc group having a closed subgroup

H \leq G

admitting a nondiscrete compactly generated topologically simple quotient, then

G \notin E

. Therefore, the only compactly generated topologically simple groups in

E

are discrete. On the other hand, the class

E

contains numerous topologically simple groups that are not compactly generated, e.g. simple groups that are regionally elliptic, i.e., groups that can be written as a directed union of compact open subgroups. Those groups have decomposition rank 2. Explicit examples appear in

[88, § 3]

[19, § 6]

2.3. More on chief factors

The existence of essentially chief series prompts us to ask whether the chief factors of

G

depend upon the choice of a specific normal series in Theorem 2.1. It is tempting to tackle that question by invoking arguments Ã la Jordan-HÃ¶lder. A technical obstruction for doing so is that the product of two closed normal subgroups need not be closed More generally, given closed subgroups

A, N

G

such that

N

is normal, the product

A N

need not be closed so that the natural abstract isomorphism

A / A \cap N \to A N / N

need not be a homeomorphism. It is a continuous injective homomorphism of the locally compact group

A / A \cap N

to a dense subgroup of the locally compact group

\bar{A N} / N

. This illustrates the necessity of considering dense embeddings of locally compact groups. We shall come back to this theme in Section 3.1 below. In the context of chief factors, this has led Reid-Wesolek to define an equivalence relation on nonabelian chief factors of

G

, called association, defined as follows: the chief factors

K_{1} / L_{1}

and

K_{2} / L_{2}

are associated if

\bar{K_{1} L_{2}} = \bar{K_{2} L_{1}}

and

K_{i} \cap \bar{L_{1} L_{2}} = L_{i}

for

i = 1, 2

. In that case

K_{1} / L_{1}

and

K_{2} / L_{2}

both embed continuously as dense normal subgroups in

\bar{K_{1} K_{2}} / \bar{L_{1} L_{2}}

. We also recall that the quasicenter of a locally compact group

G

, denoted by

Q Z (G)

, is the collection of elements whose centralizer is open. It is a topologically characteristic (not necessarily closed) subgroup of

G

containing all the discrete normal subgroups. It was first introduced
by M. Burger and S. Mozes [14]. Every nontrivial tdlcsc group with a dense quasicenter is elementary of decomposition rank 2 (see [62, LEM. 5]).

Theorem 2.4 (See [62, cor. 5]). Let

G

be a compactly generated tdlc group and let

{1} = A_{0} < A_{1} < A_{2} < \dots < A_{m} = G

and

{1} = B_{0} < B_{1} < B_{2} < \dots < B_{n} = G

be essentially chief series for

G

. Then for each

i \in {0, 1, \dots, m}

, if

A_{i} / A_{i - 1}

is a chief factor with a trivial quasicenter, there is a unique

j

such that

B_{j} / B_{j - 1}

is a chief factor with a trivial quasicenter that is associated with

A_{i} / A_{i - 1}

. In other words, the association relation establishes a bijection between the sets of chief factors with a trivial quasicenter appearing respectively in the two series.

The natural next question is to ask what can be said about chief factors. By the discussion above, one should focus on properties that are invariant under the association relation. Following Reid-Wesolek, an association class of nonabelian chief factors is called a chief block, and a group property shared by all members of a chief block is called a block property. The following are shown in [63] to be block properties: compact generation, amenability, having a trivial quasicenter, having a dense quasicenter, being elementary of a given decomposition rank.

As mentioned above, every chief factor is topologically characteristically simple. In particular, a compactly generated chief factor is subjected to the following description.

Theorem 2.5 (See [23, COR. D] and [22, REM. 3.10]). Let G be a compactly generated nondiscrete, noncompact tdlc group which is topologically characteristic simple. Then there is a compactly generated nondiscrete topologically simple tdlc group

S

, an integer

d \geq 1

and an injective continuous homomorphism

S^{d} = S \times \dots \times S \to G

of the direct product of

d

copies of

S

, such that the image of each simple factor is a closed normal subgroup of

G

, and the image of the whole product is dense.

In the setting of Theorem 2.5, we say that

G

is the quasiproduct

d

copies of the simple group

S

. Theorem 2.5 provides a major incentive to study the compactly generated nondiscrete topologically simple tdlc groups. We shall come back to this theme in Section 3 below.

Developing a meaningful structure theory for topologically characteristically simple tdlc groups that are not compactly generated is very challenging. Remarkably, significant results have been established by Reid-Wesolek [63] under the mild assumption of second countability (abbreviated sc). In spite of the noncompact generation, they introduce an appropriate notion of chief blocks, and show that there are only three possible configurations for the arrangement of chief blocks in a topologically characteristically simple tdlcsc group

G

, that they call weak type, semisimple type, and stacking type. Moreover, if

G

is of weak type, then it is automatically elementary of decomposition rank

\leq ω + 1

. The topologically characteristically simple groups

M (p)

and

H (p)

appearing in Examples 2.2 and 2.3 above are respectively of semisimple type and stacking type. We refer to [63] and [62] for details.

3. SIMPLE GROUPS

Let

S

be the class of nondiscrete, compactly generated, topologically simple locally compact groups and

S_{td}

be the subclass consisting of the totally disconnected members of

S

. By the Gleason-Yamabe theorem [73, Ñ‚Ð½. 6.0.11], all elements of

S ∖ S_{td}

are connected simple Lie groups. Prominent examples of groups in

S_{t d}

are provided by simple algebraic groups over non-Archimedean local fields, irreducible complete Kac-Moody groups over finite fields, certain groups acting on trees and many more, see [28, APPENDIX A]. A systematic study of the class

S_{td}

as a whole has been initiated by Caprace-Reid-Willis in [28], and continued with P. Wesolek in [29] and with A. Le Boudec in [22]. We now outline some of their contributions. Another survey of the properties of nondiscrete simple locally compact groups can be consulted in [17]; the present account emphasizes more recent results.

3.1. Dense embeddings and local structure

As mentioned in Section 2.3 above, the failure of the second isomorphism theorem for topological groups naturally leads one to consider dense embeddings, i.e., continuous injective homomorphisms with dense image. If

G, H

are locally compact groups and

ψ

H \to G

is a dense embedding, and if

G

is a connected simple Lie group or a simple algebraic group over a local field, then

H

is discrete or

ψ

is an isomorphism (see [29, Â§3]). This property however generally fails for groups

G \in S

; see [50] for explicit examples. Nevertheless, as soon as the group

H

is nondiscrete, it turns out that key structural features of

G

are inherited by the dense subgroup

H

. To state this more precisely, we recall the definition of the class

R

of robustly monolithic groups, introduced in [29]. A tdlc group

G

is robustly monolithic if the intersection

M

of all nontrivial closed normal subgroups of

G

is nontrivial, if

M

is topologically simple and if

M

has a compactly generated open subgroup without any nontrivial compact normal subgroup. The class

R

contains

S_{t d}

and that inclusion is strict. The following result provides the main motivation to enlarge one's viewpoint by considering

R

instead of the smaller class

S_{t d}

Theorem 3.1 (See [29, Ñ‚Ð½. 1.1.2]). Let

G, H

be tdlc groups and

ψ : H \to G

be a dense embedding. If

G \in R

and

H

is nondiscrete, then

H \in R

We emphasize that in general

H

is not topologically simple even in the special case where

G \in S_{t d}

The approach in studying the classes

S_{td}

and

R

initiated in [28] is based on the concept of locally normal subgroup, defined as a subgroup whose normalizer is open. To motivate it, recall once more that if

M, N

are closed normal subgroups of a tdlc group

G

, then the normal subgroup

M N

need not be closed. On the other hand, if

U \leq G

is a compact open subgroup, then

M \cap U

and

N \cap U

are closed normal subgroups of the compact group

U

(hence they are both locally normal), so that the product

(M \cap U) (N \cap U)

is closed. This observation motivates the definition of the structure lattice

L N (G)

of a tdlc group

G

first introduced in [27], defined as the set of closed locally normal subgroups of

G

, divided by the local equivalence relation

\sim

, where

H \sim K

H \cap K

is relatively open both in

H

and in

K

. The local class of a closed locally normal subgroup

K

is denoted by

[K]

. We also set

0 = [{1}]

and

\infty = [G]

. The structure lattice carries a natural

G

-invariant order relation defined by the inclusion of representatives. The poset

L N (G)

is a modular lattice (see [27, LEM. 2.3]). The greatest lower bound and least upper bound of two elements

α, β \in L N (G)

are respectively denoted by

α \land β

and

α \lor β

. When

G

is a

p

-adic Lie group, the structure lattice

L N (G)

can naturally be identified with the lattice of ideals in the

Q_{p}

-Lie algebra of

G

. The theory developed in [27] reveals that the structure lattice is especially well-behaved when the tdlc group

G

[A]

-semisimple, i.e.,

Q Z (G) = {1}

and the only abelian locally normal subgroup of

G

{1}

. That term is motivated by the fact that if

G

is a

p

-adic Lie group, then it is [A]-semisimple if and only if

Q Z (G) = {1}

and the

Q_{p}

-Lie algebra of

G

is semisimple, see [27, PRoP. 6.18]. An important result of P. Wesolek is that the quotient

G / R_{E} (G)

of every tdlcsc group

G

by its elementary radical is [A]-semisimple (see [82, coR. 9.15]), so that every nonelementary group has a nontrivial [A]-semisimple quotient. The following result shows that [A]-semisimplicity is automatically fulfilled by groups in

R

Theorem 3.2 (See [28, Ñ‚Ð½. A] and [29, Ñ‚Ð½. 1.2.5]). Every group

G \in R

is [A]-semisimple.

Given an [A]-semisimple tdlc group

G

, two closed locally normal subgroups

H

K \leq G

that are locally equivalent have the same centralizer; moreover, they commute if and only if their intersection is trivial (see [27, Ñ‚Ð½. 3.19]). This ensures that the map

L N (G) \to L N (G) : [K] \mapsto [K]^{⊥} = [C_{G} (K)]

is well defined, and that

α \land α^{⊥} = 0

for all

α \in L N (G)

. This allows one to define the centralizer lattice of

G

by setting

L C (G) =

{α^{⊥} ∣ α \in L N (G)}

. If

G

is [A]-semisimple, the centralizer lattice

L C (G)

is a Boolean algebra (see [27, TH. II]). We denote its Stone dual by

Ω_{G}

. Thus

Ω_{G}

is a totally disconnected compact space endowed with a canonical continuous

G

-action by homeomorphisms. In general, the

G

-action on

Ω_{G}

need not be faithful. Actually, if

L C (G) = {0, \infty}

then

Ω_{G}

is a singleton. This happens if and only if any two non-trivial closed locally normal subgroups of

G

have a nontrivial intersection. The following result shows that the dynamics of the

G

-action on

Ω_{G}

has remarkable features.

Theorem 3.3 (See [28, Ñ‚Ð½. J] and [29, Ñ‚Ð½. 1.2.6]). Let

G \in R

. Then the

G

-action on

Ω_{G}

is minimal, strongly proximal, and has a compressible open set. Moreover, the

G

-action on

Ω_{G}

is faithful if and only if

L C (G) \neq {0, \infty}

Recall that a compact

G

-space

X

is called minimal if every

G

-orbit is dense. It is called strongly proximal if the closure of each

G

-orbit in the space of probability measures on

X

contains a Dirac mass. A nonempty subset

α

X

is called compressible if for every nonempty open subset

β \subseteq X

there exists

g \in G

with

g α \subseteq β

. Obviously, if

X

is a minimal strongly proximal compact

G

-space and if

G

fixes a probability measure on

X

, then

X

is a singleton. Therefore, the following consequence of Theorem 3.3 is immediate.

Corollary 3.4. Let

G \in R

. If

G

is amenable, then

L C (G) = {0, \infty}

A local isomorphism between tdlc groups

G_{1}, G_{2}

is a triple (

φ, U_{1}, U_{2}

) where

U_{i}

is an open subgroup of

G_{i}

and

φ : U_{1} \to U_{2}

is an isomorphism of topological groups. We
emphasize that the structure lattice and the centralizer lattice are local invariants: they only depend on the local isomorphism class of the ambient tdlc group. However, for a group

G \in R

, the compact

G

-space

Ω_{G}

can also be characterized by global properties among all compact

G

-spaces. In order to be more precise, let us first recall some terminology. Given an action of a group

G

by homeomorphisms on a Hausdorff topological space

X

, we define the rigid stabilizer

{Rist}_{G} (U)

of a subset

U \subseteq X

as the pointwise stabilizer of the complement of

U

X

. The

G

-action on

X

is called microsupported if for every nonempty open subset

U \subset X

with

U \neq X

, the rigid stabilizer

{Rist}_{G} (U)

acts nontrivially on

X

. The term "microsupported" was first coined in [28], although the notion it designates has frequently appeared in earlier references, notably in the work of M. Rubin on reconstruction theorems (see [67] and references therein). A prototypical example of a microsupported action of a tdlc group is given by the action of the full automorphism group

Aut (T)

of a locally finite regular tree

T

of degree

\geq 3

on the compact space

\partial T

consisting of the ends of

T

. The following result shows that for a general group

G \in R

, the

G

-action on

Ω_{G}

shares many dynamical properties with the

Aut (T)

-action on

\partial T

Theorem 3.5 (See [28, Ñ‚Ð½. J], [29, Ñ‚Ð½. 7.3.3] and [22, Ñ‚Ð½. 7.5]). Let

G \in R

. Then the G-action on

Ω_{G}

is microsupported. Moreover, for each nonempty microsupported compact

G

-space

X

on which the

G

-action is faithful, there is a G-equivariant continuous surjective map

Ω_{G} \to X

. In particular, the

G

-action on

X

is minimal, strongly proximal, and has a compressible open set.

This shows that

Ω_{G}

is universal among the faithful microsupported compact

G

-spaces; in particular, the purely local condition that

L C (G) = {0, \infty}

ensures that

G

does not have any faithful microsupported continuous action on any compact space. Theorem 3.5 was first established for totally disconnected compact

G

-spaces in [28,29], and then extended to all compact

G

-spaces in [22], using tools from topological dynamics. Further properties of the

G

-space

Ω_{G}

and on the algebraic structure of groups in

R

can be consulted in those references.

We now present another aspect of the local approach to the structure of simple tdlc groups. We define the local prime content of a tdlc group

G

, denoted by

π (G)

, to be the set of those primes

p

such that every compact open subgroup

U \leq G

contains an infinite pro-

p

subgroup.

Theorem 3.6 (See [28, TH. H] and [29, coR. 1.1.4 AND TH. 1.2.1]). The following assertions hold for any group

G \in R

(i) The local prime content

π (G)

is finite and nonempty.

(ii) For each

p \in π (G)

, there is a group

G_{(p)} \in R

that is locally isomorphic to a pro-p group, and a dense embedding

G_{(p)} \to G

(iii) If

H

is a tdlc group acting continuously and faithfully by automorphisms on

G

, then

H

is locally isomorphic to a pro-

π (G)

group.

Roughly speaking, Theorem 3.6(ii) asserts that every group in

R

can be "approximated" by a locally pro-

p

group in

R

. The restriction on the automorphism group of a group in

R

from Theorem 3.6(iii) should be compared with the automorphism group of the restricted product

M (p)

from Example 2.2. Indeed, the Polish group

Sym (Z)

embeds continuously in

Aut (M (p))

by permuting the simple factors, and every tdlcsc group continuously embeds in

Sym (Z)

. In some sense, the construction of stacking type chief factors in Example 2.3 crucially relies on the hugeness of the group

Aut (M (p))

. Theorem 3.6(iii) shows that the automorphism group of a group in

R

is considerably smaller.

Let us finish this subsection with a brief discussion of classification problems. The work of S. Smith [72] shows that

S_{td}

contains uncountably many isomorphism classes; his methods of proof suggest that the isomorphism relation on

S_{td}

has a similar complexity as the isomorphism relation on the class of finitely generated discrete simple groups. This provides evidence that the problem of classifying groups in

S_{td}

up to isomorphism is illposed. The recent results on the local structure of groups in

S_{td}

or in

R

may be viewed as a hint to the fact the local isomorphism relation might be better behaved (see [29, Ñ‚Ð½. 1.1.5]). At the time of this writing, we do not know whether or not the groups in

S_{td}

fall into countably many local isomorphism classes. However, classifying simple groups up to isomorphism remains a pertinent problem for some significant subclasses of

S_{td}

. To wit, let us mention that, by [30, coR. 1.4], a group

G \in S_{td}

is isomorphic to a simple algebraic group over a local field if and only if it is locally isomorphic to a linear group, i.e., a subgroup of

{G L}_{d} (k)

for some integer

d

and some locally compact field

k

. Lastly, a remarkable classification theorem concerning an important class of nonlinear simple groups acting on locally finite trees has been obtained by N. Radu [61]. It would be highly interesting to extend Radu's results by classifying all groups in

S_{td}

acting properly and continuously by automorphisms on a given locally finite tree

T

in such a way that the action on the set of ends of

T

is doubly transitive. That class is denoted by

S_{T}

. Results from [25] ensure that the isomorphism relation restricted to

S_{T}

is smooth (see [37, DEFINITION 5.4.1]), which means that it comes at the bottom of the hierarchy of complexity of classification problems in the formalism established by invariant

not know whether there is a tree

T

such that

S_{T}

contains uncountably many isomorphism classes.

3.2. Applications to lattices

The study of lattices in semisimple Lie and algebraic groups has known tremendous developments since the mid-20th century, with Margulis' seminal contributions as cornerstones. Remarkably, several key results on lattices have been established at a high level of generality, well beyond the realm of linear groups. An early illustration is provided by [13]. More recently, Y. Shalom [70] and Bader-Shalom [5] have established an extension of Margulis' Normal Subgroup Theorem valid for all irreducible cocompact lattices in products of groups in

S

, while various analogues of Margulis' superrigidity for irreducible lattices in products have been established for various kinds of target spaces, see

[3, 4, 31, 36, 38, 55, 56, 70]

. Those results have in common that they rely on transcendental methods: they use a mix
of tools from ergodic theory, probability theory, and abstract harmonic analysis, but do not require any detailed consideration of the algebraic structure of the ambient group. Another breakthrough in this field was accomplished by M. Burger and S. Mozes [15], who constructed a broad family of new finitely presented infinite simple groups as irreducible lattices in products of nonlinear groups in

S_{td}

. Their seminal work involves a mix of transcendental methods together with a fair amount of structure theory developed in [14].

The following two recent results rely in an essential way on the properties of the class

S_{t d}

outlined above.

Theorem 3.7 (See [21, Ñ‚Ð½. A]). Let

n \geq 2

be an integer, let

G_{1}, \dots, G_{n} \in S_{td}

and

Γ \leq G =

G_{1} \times \dots \times G_{n}

be a lattice such that the projection

p_{i} (Γ)

is dense in

G_{i}

for all

i

. Assume that

Γ

is cocompact, or that

G

has Kazhdan's property

(T)

. Then the set of discrete subgroups of

G

containing

Γ

is finite.

Theorem 3.8 (See [21, Ñ‚Ð½. c]). Let

n \geq 2

be an integer and let

G_{1}, \dots, G_{n} \in S_{t d}

be compactly presented. For every compact subset

K \subset G = G_{1} \times \dots \times G_{n}

, the set of discrete subgroups

Γ \leq G

with

G = K Γ

and with

p_{i} (Γ)

dense in

G_{i}

for all

i

, is contained in a union of finitely many

Aut (G)

-orbits.

For a detailed discussion of the notion of compactly presented locally compact groups, we refer to

[32, c H .8

Theorems 3.7 and 3.8 can be viewed as respective analogues of two theorems of H. C. Wang

[78, 79]

on lattices in semisimple Lie groups and reveal the existence of positive lower bounds on the covolume of certain families of irreducible cocompact lattices. It should be underlined that the corresponding statements fail for lattices in a single group

G \in S_{t d}

, see [6, Ñ‚Ð½. 7.1]. Theorem 3.8 is established by combining Theorem 3.7 with recent results on local rigidity of cocompact lattices in arbitrary groups, due to Gelander-Levit [39].

3.3. Applications to commensurated subgroups

The structure theory of tdlc groups provides valuable tools in exploring the so-called commensurated subgroups of an abstract group. In this section, we recall that connection and illustrate it with several recent results. Further results on commensurated subgroups will be mentioned in Section 4 below.

Let

Γ

be a group. Two subgroups

Λ_{1}, Λ_{2} \leq Γ

are called commensurate if their intersection

Λ_{1} \cap Λ_{2}

has finite index both in

Λ_{1}

and in

Λ_{2}

. The commensurator of a subgroup

Λ \leq Γ

, denoted by

{Comm}_{Γ} (Λ)

, is the set of those

γ \in Γ

such that

Λ

and

γ Λ γ^{- 1}

are commensurate. It is easy to see that

{Comm}_{Γ} (Λ)

is a subgroup of

Γ

containing the normalizer

N_{Γ} (Λ)

. The commensurator has naturally appeared in group theory; one of its early occurrences is in Mackey's irreducibility criterion for induced unitary representations (see [51]). It also appears in a celebrated characterization of arithmetic lattices in semisimple groups due to Margulis [53, ÑH.

I x, T H

. (B)]. A commensurated subgroup of

Γ

is a subgroup

Λ \leq Γ

such that

{Comm}_{Γ} (Λ) = Γ

. Clearly, every normal subgroup of

Γ

is commensurated; more generally, every subgroup that is commensurate to a normal subgroup is commensurated.

Those commensurated subgroups are considered as trivial. For example, finite subgroups and subgroups of finite index are always commensurated subgroups. It is however important to underline that commensurated subgroups are not all of this trivial form. Indeed, an easy but crucial observation is that compact open subgroups are always commensurated. In particular, in the simple group

{P S L}_{2} (Q_{p})

, the subgroup

{P S L}_{2} (Z_{p})

(which is obviously not commensurate to any normal subgroup of

{P S L}_{2} (Q_{p})

) is commensurated.

Let us next remark that if

U

is a commensurated subgroup of a group

G

and

φ : Γ \to G

is a group homomorphism, then

φ^{- 1} (U)

is a commensurated subgroup of

Γ

. This is the case in particular if

G

is a tdlc group and

U \leq G

is a compact open subgroup. A fundamental observation is that all commensurated subgroups of

Γ

arise in this way. More, precisely, a subgroup

Λ \leq Γ

is commensurated if and only if there is a tdlc group

G

, a compact open subgroup

U \leq G

, and a homomorphism

φ : Γ \to G

with dense image such that

φ^{- 1} (U) = Λ

. Indeed, given a commensurated subgroup

Λ \leq Γ

, then

Λ

acts on the coset space

Γ / Λ

with finite orbits, so that the closure of the natural image of

Γ

in the permutation group

Sym (Γ / Λ)

, endowed with the topology of pointwise convergence, is a tdlc group containing the closure of the image of

Λ

as a compact open subgroup. That tdlc group is called the Schlichting completion of the pair

(Γ, Λ)

, denoted by

Γ / / Λ

. We refer to [68], [71, SECTION 3] and [65] for more information. Let us merely mention here that a commensurated subgroup

Λ \leq Γ

is commensurate to a normal subgroup if and only if the Schlichting completion

G = Γ / / Λ

is compact-by-discrete, i.e.,

G

has a compact open normal subgroup (see [22, LEM. 5.1]).

The occurrence of nontrivial commensurated subgroups in finitely generated groups with few normal subgroups (e.g., simple groups, or just-infinite groups, i.e., groups all of whose proper quotients are finite) remains an intriguing phenomenon. On the empirical basis of the known examples, it seems to be rather rare. The following result provides valuable information in that context.

Theorem 3.9 (See [22, Ñ‚Ð½. 5.4]). Let

Γ

be a finitely generated group. Assume that all normal subgroups of

Γ

are finitely generated, and that every proper quotient of

Γ

is virtually nilpotent. Let also

X

be a compact

Γ

-space on which the

Γ

-action is faithful, minimal and microsupported. Assume that at least one of the following conditions is satisfied:

(1)

Γ

is residually finite.

(2)

Γ

fixes a probability measure on

X

Then every commensurated subgroup of

Γ

is commensurate to a normal subgroup.

This applies to all finitely generated branch groups, as well as to numerous finitely generated almost simple groups arising in Cantor dynamics, and whose study has known spectacular recent developments (see [34,59] and references therein). We refer to [22] for details and a more precise description of those applications.

Let us briefly outline how the proof of Theorem 3.9 works in the case where

Γ

fixes a probability measure on

X

. Let

Λ \leq Γ

be a commensurated subgroup and

G = Γ / / Λ

be the
corresponding Schlichting completion. That

Γ

is finitely generated implies that

G

is compactly generated. The hypotheses made on the normal subgroup structure of

Γ

yield some restrictions on the essentially chief series of

G

afforded by Theorem 2.1. More precisely, assuming by contradiction that

Λ

is not commensurate to a normal subgroup, then the upper most chief factor

K / L

with trivial quasicenter in an essentially chief series for

G

must be compactly generated. Its structure is therefore described by Theorem 2.5. A key point in the proof, relying on various ingredients from topological dynamics and involving detailed considerations of the Chabauty space of closed subgroups of

Γ

and

G

, is to show that the given

Γ

-action on

X

gives rise to a continuous, faithful, microsupported

G / L

-action on a compact space

Y

which is closely related to the original space

X

. Invoking (a suitable version of) Theorem 3.5 for the chief factor

K / L

ensures that

Y

has a compressible open set, from which it follows that

X

has a compressible open set for the

Γ

-action. This finally contradicts the hypothesis of existence of a

Γ

-invariant probability measure.

4. SCALE METHODS

The scale of a tdlc group endomorphism,

α

, is a positive integer that conveys information about the dynamics of the action of

α

. Roughly speaking,

α

contracts towards the identity on one subgroup of

G

and expands on another, and the scale is the expansion factor This section gives an account of properties of the scale and descriptions of the action of

α

on certain associated subgroups of

G

which, when applied to inner automorphisms, answer questions about group structure.

Let

α : G \to G

be a continuous endomorphism. The scale of

α

s (α) = min {[α (U) : α (U) \cap U] ∣ U \leq G compact and open}

This value is a positive integer because

α (U) \cap U

is an open subgroup of the compact group

α (U)

. Subgroups at which the minimum is attained are said to be minimizing for

α

. The following results from

[85, 86, 89]

relate minimizing subgroups to the dynamics of

α

Theorem 4.1. Let

α

be a continuous endomorphism of the tdlc group

G

and let

U \leq G

be compact and open. Define subgroups

\begin{aligned} U_{+} = {u \in U ∣ \exists {u_{n}}_{n \geq 0} \subset U with u_{0} = u and u_{n} = α (u_{n + 1})} \\ U_{-} = {u \in U ∣ α^{n} (u) \in U for all n \geq 0} . \end{aligned}

Also define the subgroup

U_{- -} = ⋃_{n \geq 0} α^{- n} (U_{-})

of G.

Then

U

is minimizing for

α

if and only if

(TA)

U = U_{+} U_{-}

and (TB)

U_{-}

is closed.

A compact open subgroup

U

satisfying

T A

and

T B

is said to be tidy for

α

, and

s (α) = [α (U_{+}) : U_{+}]

for any such subgroup

U

. Tidiness has two further dynamical interpretations: (1) an

α

-trajectory

{α^{n} (g)}_{n \geq 0}

cannot return to a tidy subgroup once it departs; and (2) when

α

is an automorphism,

U

is tidy for

α

if and only if the orbit

{α^{n} (U)}_{n \in Z}

is a
geodesic for the metric

d (U, V) = \log [U : U \cap V] + \log [V : U \cap V]

on the set of compact open subgroups of

G

Note that every compact open subgroup of

G

has a subgroup

U

for which

T A

holds and, if

α

is the inner automorphism

α_{g} (x) := g x g^{- 1}

, then property

T A

implies that

U g^{m} U g^{n} U = U g^{m + n} U

for all

m, n \geq 0

. These points were already used in [12] in the proof that a reductive group over a locally compact field of positive characteristic is type I, where they were observed to hold in such groups.

In the following compilation of results from

[54, 85, 86, 89], Δ

denotes the modular function on the automorphism group of

G

Theorem 4.2. The scale

s : End (G) \to Z^{+}

satisfies:

(i)

s (α) = 1

if and only if there is a compact open subgroup

U \leq G

with

α (U) \leq U

;

(ii)

s (α) = lim_{n \to \infty} {[α^{n} (V) : α^{n} (V) \cap V]}^{\frac{1}{n}}

for every compact open

V \leq G

, and

s (α^{n}) = s (α)^{n}

for every

n \geq 0

; and

(iii) if

α

is an automorphism, then

Δ (α) = s (α) / s (α^{- 1})

The function

s \circ α_{∙} : G \to Z^{+}

, with

α_{g} (x) = g x g^{- 1}

, is continuous for the group topology on

G

and the discrete topology on

Z^{+}

Continuity of

s \circ α_{∙}

is implied by the fact that, if

U

is tidy for

g

, then

U

is also tidy for all

h \in U g U

and

s (h) = s (g)

, [85, THEOREM 3].

Questions about the structure of tdlc groups may be answered with scale and tidy subgroup techniques. K. H. Hofmann and A. Mukherjea conjectured in [45] that all locally compact groups are "neat"-a property involving the conjugation action by a single element

g

. They used approximation by Lie groups to reduce to the totally disconnected case, and subgroups tidy for

g

are used in [47] to show that all groups are neat. Answering another question of K.H. Hofmann, the set

per (G)

, comprising those elements of

G

such that the closure of

⟨ g ⟩

is compact, is shown in [84] to be closed by appealing to the properties of the scale given in Theorem 4.2.

The scale and the subgroup

U_{+}

associated with it in Theorem 4.1 are given a concrete representation in [9]. Put

U_{+ +} = ⋃_{n \geq 0} α^{n} (U_{+})

. Then

U_{+ +}

is closed if

U

is tidy and

U_{+ +} ⋊ ⟨ α ⟩

acts on a regular tree with valency

s (α) + 1

: the image of

U_{+ +} ⋊ ⟨ α ⟩

is a closed subgroup of the isometry group of the tree; is transitive on vertices; and fixes an end of the tree. The resulting isometry groups of trees correspond to the self-replicating groups studied in [58]. Moreover, the semidirect product

U_{+ +} ⋊ ⟨ α ⟩

also belongs to the family of focal hyperbolic groups studied in [18].

4.1. Contraction and other groups

Subgroups of

G

defined in terms of the action of

α

are related to the scale and tidy subgroups. It is convenient to confine the statements to automorphisms here. Extensions to endomorphisms may be found in

[16, 89]

The contraction subgroup for

α \in Aut (G)

con (α) = {x \in G ∣ α^{n} (x) \to 1 as n \to \infty}

The next result, from

[9, 46]

, relates contraction subgroups to the scale.

Theorem 4.3. Let

α \in Aut (G)

. Then

⋂ {U_{- -} ∣ U

is tidy for

α}

is equal to

\bar{con (α)}

, and

s (α^{- 1})

is equal to the scale of the restriction of

α^{- 1}

\bar{con (α)}

. Hence

s (α^{- 1}) > 1

if and only if

\bar{con (α)}

is not compact.

G

is a

p

-adic Lie group, then

con (α)

is closed for every

α

, [80], but that is not the case if, for example,

G

is the isometry group of a regular tree, or a certain type of complete Kac-Moody group [7], or if

L E (G) \neq {0, \infty}

[28]. The closedness of con

(α)

is equivalent, by [9, THEOREM 3.32], to the triviality of the

n u b

subgroup,

nub (α) = ⋂ {U ∣ U tidy for α}

The nub for

α

is compact and is the largest

α

-stable subgroup of

G

on which

α

acts ergodically, which sharpens the theorem of N. Aoki in [2] that a totally disconnected locally compact group with an ergodic automorphism must be compact. P. Halmos had asked in [44] whether that was so for all locally compact groups. See [48,90] for the connected case, and also [60].

The structure of closed contraction subgroups con

(α)

is described precisely in [40] If

con (α)

is closed, there is a composition series

{1} = G_{0} ◃ \dots ◃ G_{n} = con (α)

α

-stable closed subgroups of

con (α)

such that the factors

G_{i + 1} / G_{i}

have no proper, nontrivial

α

-stable closed subgroups. The factors appearing in any such series are unique up to permutation and isomorphism, and their isomorphism types come from a countable list: each torsion factor being a restricted product

⨁_{i \in Z} (G_{i}, U_{i})

with

G_{i} = F

, a finite simple group, and

U_{i} = F

i \geq 0

and trivial if

i < 0

, and the automorphism the shift; and each divisible factor being a

p

-adic vector group and the automorphism a linear transformation. Moreover, con

(α)

is the direct product

T \times D

with

T

a torsion and

D

a divisible

α

-stable subgroup. The divisible subgroup

D

is a direct product

D_{p_{1}} \times \dots \times D_{p_{r}}

with

D_{p_{i}}

a nilpotent

p

-adic Lie group for each

p_{i}

. The torsion group

T

may include nonabelian irreducible factors but, should it happen to be locally pro-

p

, then it is nilpotent too, see [42]. The number of nonisomorphic locally pro-

p

closed contraction groups is uncountable [41].

Contraction groups correspond to unipotent subgroups of algebraic groups and, following [75], the Tits core,

G^{†}

, of the tdlc group

G

is defined to be the subgroup generated by all closures of contraction groups. It is shown in [26] that, if

G

is topologically simple, then

G^{†}

is either trivial or is abstractly simple and dense in

G

The correspondence with algebraic groups is pursued in [9], where the parabolic subgroup for

α \in Aut (G)

is defined to be

par (α) = {x \in G ∣ {α^{n} (x)}_{n \geq 0} has compact closure}

and the Levi factor to be

lev (α) = par (α) \cap par (α^{- 1})

. Then

par (α)

, and hence

lev (α)

, is closed in

G

, [85, PRoposition 3]. It may be verified that

con (α) ◃ par (α)

and shown, see [9], that

par (α) = lev (α) con (α)

4.2. Flat groups of automorphisms

A group,

H

, of automorphisms of

G

is flat if there is a compact open subgroup,

U \leq G

, that is tidy for every

α \in H

. The stabilizer of

U

H

is called the uniscalar subgroup and denoted

H_{u}

. The factoring of subgroups tidy for a single automorphism in Theorem 4.1 extends to flat groups as follows.

Theorem 4.4 ([87]). Let

H

be a finitely generated flat group of automorphisms of

G

and suppose that

U

is tidy for

H

. Then

H_{u} ◃ H

and there is

r \geq 0

such that

H / H_{u} ≅ Z^{r}

There are $q \geq 0$ and closed groups $U_{j} \leq U, j \in {0, 1, \dots, q}$ such that $α (U_{0}) = U_{0}; α (U_{j})$ is either a subgroup or supergroup of $U_{j}$ for every $j \in {1, \dots, q}$ ; and $U = U_{0} U_{1} \dots U_{q}$ .
${\tilde{U}}_{j} := ⋃_{α \in H} α (U_{j})$ is a closed subgroup of G for each $j \in {1, \dots, q}$ .
There are, for each $j \in {1, \dots, q}$ , an integer $s_{j} > 1$ and a surjective homomorphism $ρ_{j} : H \to (Z, +)$ such that $Δ ({α |}_{{\tilde{U}}_{j}}) = s_{j}^{ρ_{j} (α)}$ .
The integers $r$ and $q$ , and integers $s_{j}$ and homomorphisms $ρ_{j}$ for each $j \in {1, \dots, q}$ , are independent of the subgroup $U$ tidy for $H$ .

The number

r

in Theorem 4.4 is the flat rank of

H

. The singly-generated group

⟨ α ⟩

has flat rank equal to 0 if

α

is uniscalar and 1 if not. Flat groups of automorphisms with rank at least 1 correspond to Cartan subgroups in Lie groups over local fields and may be interpreted geometrically in terms of apartments in isometry groups of buildings [8].

More generally, flatness of groups of automorphisms may be shown by the following converse to the fact that flat groups are abelian modulo the stablizer of tidy subgroups.

Theorem 4.5 ([87][71]). Every finitely generated nilpotent subgroup of

Aut (G)

is flat, and every polycyclic subgroup is virtually flat.

Flatness is used-in combination with bounded generation of arithmetic groups [57,74], the fact that almost normal subgroups are close to normal [11], and the Margulis normal subgroup theorem [53]-to prove the Margulis-Zimmer conjecture in the special case of Chevalley groups in [71] and show that there are no commensurated subgroups of arithmetic subgroups other than the natural ones.

5. FUTURE DIRECTIONS

The contributions to the structure theory of tdlc groups surveyed in this article highlight that, for a general tdlc group

G

, as soon as the topology is nondiscrete, its interaction with the group structure yields significant algebraic constraints. As mentioned in the introduction, we view the dynamics of the conjugation action as a unifying theme of our considerations. The results we have surveyed reveal that those dynamics tend to be richer
than one might expect. This is especially the case among tdlc groups that are nonelementary. We hope that further advances will shed more light on this paradigm in the future.

Concerning decomposition theory, it is an important open problem to clarify what distinguishes elementary and nonelementary tdlc groups. A key question asks whether every nonelementary tdlcsc group

G

contains a closed subgroup

H

admitting a quotient in

S_{td}

. Concerning simple groups, our results yield a dichotomy, depending on whether the centralizer lattice is trivial or not. The huge majority of known examples of groups in

S_{td}

(listed in [28, APPENDIX A]) have a nontrivial centralizer lattice, the most notable exceptions being the simple algebraic groups over local fields. Finding new groups in

S_{t d}

with a trivial centralizer lattice would be a decisive step forward. A fundamental source of examples of tdlc groups is provided by Galois groups of transcendental field extensions with finite transcendence degree (see [66, TH. 2.9], highlighting the occurrence of topologically simple groups), but this territory remains largely unexplored from the viewpoint of structure theory of tdlc groups. Concerning scale methods, the structure of tdlc groups all of whose elements are uniscalar (i.e., have scale 1) is still mysterious. In particular, we do not know whether every such group is elementary. This is equivalent to asking whether a tdlc group, all of whose closed subgroups are unimodular, is necessarily elementary. A positive answer would provide a formal incarnation to the claim that the dynamics of the conjugation action is nontrivial for all nonelementary tdlc groups. We refer to [24] for a more extensive list of specific problems.

We believe that a good measurement of the maturity of a mathematical theory is provided by its ability to solve problems arising on the outside of the theory. For the structure theory of tdlc groups, the Margulis-Zimmer conjecture appears as a natural target. As mentioned in Section 4, partial results in the nonuniform case, relying on scale methods on tdlc groups, have already been obtained in [71].

Another source of external problems is provided by abstract harmonic analysis. As mentioned in the introduction, the emergence of locally compact groups as an independent subject of study coincides with the foundation of abstract harmonic analysis. However, fundamental problems clarifying the links between the algebraic structure of a locally compact group and the properties of its unitary representations remain open. The class of amenable locally compact groups is defined by a representation theoretic property (indeed, a locally compact group is amenable if and only if every unitary representation is weakly contained in the regular), but purely algebraic characterizations of amenable groups are still missing. In particular, the following nondiscrete version of Day's problem is open and intriguing: Is every amenable second countable tdlc group elementary (in the sense of Section 2)? The unitary representation theory also reveals a fundamental dichotomy between locally compact groups of type

I

(roughly speaking, those for which the problem of classifying the irreducible unitary representations up to equivalence is tractable) and the others (see

[10, 35, 52]

). Algebraic characterizations of type I groups are also desirable. In particular, we underline the following question: Does every second countable locally compact group of type I contain a cocompact amenable subgroup? For a more detailed discussion of that problem and related results, we refer to [20].

ACKNOWLEDGMENTS

It is a pleasure to take this opportunity to heartily thank our collaborators, past and present, for their ideas and companionship. We are grateful to Adrien Le Boudec and Colin Reid for their comments on a preliminary version of this article.

FUNDING

This work was written while P.-E. Caprace was a Senior Research Associate of the Belgian F.R.S.-FNRS and G. A. Willis was Australian Research Council Laureate Professor under the grant FL170100032. The support of these bodies is gratefully acknowledged.

REFERENCES

[1] H. Abels, Specker-Kompaktifizierungen von lokal kompakten topologischen Gruppen. Math. Z. 135 (1973/1974), 325-361.

[2] N. Aoki, Dense orbits of automorphisms and compactness of groups. Topology Appl. 20 (1985), no. 1, 1-15.

[3] U. Bader and A. Furman, Boundaries, Weyl groups, and superrigidity. Electron. Res. Announc. Math. Sci. 19 (2012), 41-48.

[4] U. Bader and A. Furman, Boundaries, rigidity of representations, and Lyapunov exponents. In Proceedings of the International Congress of MathematiciansSeoul 2014. Vol. III, pp. 71-96, Kyung Moon Sa, Seoul, 2014.

[5] U. Bader and Y. Shalom, Factor and normal subgroup theorems for lattices in products of groups. Invent. Math. 163 (2006), no. 2, 415-454.

[6] H. Bass and R. Kulkarni, Uniform tree lattices. J. Amer. Math. Soc. 3 (1990), no. 4, 843-902.

[7] U. Baumgartner, J. Ramagge, and B. RÃ©my, Contraction groups in complete KacMoody groups. Groups Geom. Dyn. 2 (2008), no. 3, 337-352.

[8] U. Baumgartner, B. RÃ©my, and G. A. Willis, Flat rank of automorphism groups of buildings. Transform. Groups 12 (2007), no. 3, 413-436.

[9] U. Baumgartner and G. A. Willis, Contraction groups and scales of automorphisms of totally disconnected locally compact groups. Israel J. Math. 142 (2004), 221-248.

[10] B. Bekka and P. de la Harpe, Unitary representations of groups, duals, and characters. Math. Surveys Monogr. 250, American Mathematical Society, Providence, RI, 2020.

[11] G. M. Bergman and H. W. Lenstra Jr., Subgroups close to normal subgroups. J. Algebra 127 (1989), no. 1, 80-97.

[12] I. N. BernÅ¡teÄn, All reductive

p

-adic groups are of type I. Funktsional. Anal. i Prilozhen. 8 (1974), no. 2, 3-6.

[13] I. N. BernÅ¡teÄn and D. A. KaÅ¾dan, The one-dimensional cohomology of discrete subgroups. Funktsional. Anal. i Prilozhen. 4 (1970), no. 1, 1-5.

[14] M. Burger and S. Mozes, Groups acting on trees: from local to global structure. Publ. Math. Inst. Hautes Ã‰tudes Sci. 92 (2000), 113-150.

[15] M. Burger and S. Mozes, Lattices in product of trees. Publ. Math. Inst. Hautes Ã‰tudes Sci. 92 (2000), 151-194.

[16] T. P. Bywaters, H. GlÃ¶ckner, and S. Tornier, Contraction groups and passage to subgroups and quotients for endomorphisms of totally disconnected locally compact groups. Israel J. Math. 227 (2018), 691-752.

[17] P.-E. Caprace, Non-discrete simple locally compact groups. In European Congress of Mathematics, pp. 333-354, Eur. Math. Soc., ZÃ¼rich, 2018.

[18] P.-E. Caprace, Y. Cornulier, N. Monod, and R. Tessera, Amenable hyperbolic groups. J. Eur. Math. Soc. (JEMS) 17 (2015), no. 11, 2903-2947.

[19] P.-E. Caprace and T. De, Medts, Simple locally compact groups acting on trees and their germs of automorphisms. Transform. Groups 16 (2011), no. 2, 375-411.

[20] P.-E. Caprace, M. Kalantar, and N. Monod, A type I conjecture and boundary representations of hyperbolic groups. 2021, arXiv:2110.00190.

[21] P.-E. Caprace and A. Le Boudec, Bounding the covolume of lattices in products. Compos. Math. 155 (2019), no. 12, 2296-2333.

[22] P.-E. Caprace, A. Le Boudec, and D. Francoeur, Commensurated subgroups and micro-supported actions. 2020, arXiv:2002.02910. To appear in J. Eur. Math. Soc. (JEMS).

[23] P.-E. Caprace and N. Monod, Decomposing locally compact groups into simple pieces. Math. Proc. Cambridge Philos. Soc. 150 (2011), no. 1, 97-128.

[24] P.-E. Caprace and N. Monod, Future directions in locally compact groups: a tentative problem list. In New directions in locally compact groups, pp. 343-355, London Math. Soc. Lecture Note Ser. 447, Cambridge Univ. Press, Cambridge, 2018.

[25] P.-E. Caprace and N. Radu, Chabauty limits of simple groups acting on trees. J. Inst. Math. Jussieu 19 (2020), no. 4, 1093-1120.

[26] P.-E. Caprace, C. D. Reid, and G. A. Willis, Limits of contraction groups and the Tits core. J. Lie Theory 24 (2014), 957-967.

[27] P.-E. Caprace, C. D. Reid, and G. A. Willis, Locally normal subgroups of totally disconnected groups. Part I: general theory. Forum Math. Sigma 5 (2017), e11, 76.

[28] P.-E. Caprace, C. D. Reid, and G. A. Willis, Locally normal subgroups of totally disconnected groups. Part II: compactly generated simple groups. Forum Math. Sigma 5 (2017), e12, 89.

[29] P.-E. Caprace, C. Reid, and P. Wesolek, Approximating simple locally compact groups by their dense locally compact subgroups. Int. Math. Res. Not. IMRN 7 (2021), 5037-5110.

[30] P.-E. Caprace and T. Stulemeijer, Totally disconnected locally compact groups with a linear open subgroup. Int. Math. Res. Not. IMRN 24 (2015), 13800-13829.

[31] I. Chatterji, T. FernÃ³s, and A. Iozzi, The median class and superrigidity of actions on CAT(0) cube complexes. J. Topol. 9 (2016), no. 2, 349-400.

[32] Y. Cornulier and P. de la Harpe, Metric geometry of locally compact groups. EMS Tracts Math. 25, European Mathematical Society (EMS), ZÃ¼rich, 2016.

[33] M. M. Day, Amenable semigroups. Illinois J. Math. 1 (1957), 509-544.

[34] Y. de Cornulier, Groupes pleins-topologiques (d'aprÃ¨s Matui, Juschenko, Monod, ...). AstÃ©risque 361 (2014), no. 1064, viii, 183-223.

[35] J. Dixmier, Les

C^{*}

-algÃ¨bres et leurs reprÃ©sentations. Les Grands Classiques Gauthier-Villars. [Gauthier-Villars Great Classics], Ã‰ditions Jacques Gabay, Paris, 1996.

[36] E. Fioravanti, Superrigidity of actions on finite rank median spaces. Adv. Math. 352 (2019), 1206-1252.

[37] S. Gao, Invariant descriptive set theory. Pure Appl. Math. (Boca Raton) 293, CRC Press, Boca Raton, FL, 2009.

[38] T. Gelander, A. Karlsson, and G. A. Margulis, Superrigidity, generalized harmonic maps and uniformly convex spaces. Geom. Funct. Anal. 17 (2008), no. 5,

1524 - 1550

[39] T. Gelander and A. Levit, Local rigidity of uniform lattices. Comment. Math. Helv. 93 (2018), no. 4, 781-827.

[40] H. GlÃ¶ckner and G. A. Willis, Classification of the simple factors appearing in composition series of totally disconnected contraction groups. J. Reine Angew. Math. 643 (2010), 141-169.

[41] H. GlÃ¶ckner and G. A. Willis, Decompositions of locally compact contraction groups, series and extensions. J. Algebra 570 (2021), 164-214.

[42] H. GlÃ¶ckner and G. A. Willis, Locally pro-

p

contraction groups are nilpotent. J. Reine Angew. Math. (2021). DOI 10.1515/crelle-2021-0050.

[43] R. Guralnick, Applications of the classification of finite simple groups. In Proceedings of the International Congress of Mathematicians-Seoul 2014. Vol. II, pp. 163-177, Kyung Moon Sa, Seoul, 2014.

[44] P. R. Halmos, Lectures on ergodic theory. Publ. Math. Soc Jpn. 3, The Mathematical Society of Japan, 1956.

[45] K. H. Hofmann and A. Mukherjea, Concentration functions and a class of noncompact groups. Math. Ann. 256 (1981), no. 4, 535-548.

[46] W. Jaworski, On contraction groups of automorphisms of totally disconnected locally compact groups. Israel J. Math. 172 (2009), 1-8.

[47] W. Jaworski, J. Rosenblatt, and G. A. Willis, Concentration functions in locally compact groups. Math. Ann. 305 (1996), no. 4, 673-691.

[48] R. Kaufman and M. Rajagopalan, On automorphisms of a locally compact group. Michigan Math. J. 13 (1966), 373-374.

[49] V. Lafforgue, Shtukas for reductive groups and Langlands correspondence for function fields. In Proceedings of the International Congress of MathematiciansRio de Janeiro 2018. I. Plenary lectures, pp. 635-668, World Sci. Publ., Hackensack, NJ, 2018.

[50] A. Le Boudec, Groups acting on trees with almost prescribed local action. Comment. Math. Helv. 91 (2016), no. 2, 253-293.

[51] G. W. Mackey, On induced representations of groups. Amer. J. Math. 73 (1951),

576 - 592

[52] G. W. Mackey, The theory of unitary group representations. Chicago Lectures in Math., University of Chicago Press, Chicago, IL-London, 1976.

[53] G. A. Margulis, Discrete subgroups of semisimple Lie groups. Ergeb. Math. Grenzgeb. (3) [Res. Math. Related Areas (3)] 17, Springer, Berlin, 1991.

[54] R. G. MÃ¶ller, Structure theory of totally disconnected locally compact groups via graphs and permutations. Canad. J. Math. 54 (2002), 795-827.

[55] N. Monod, Superrigidity for irreducible lattices and geometric splitting. J. Amer Math. Soc. 19 (2006), no. 4, 781-814.

[56] N. Monod and Y. Shalom, Cocycle superrigidity and bounded cohomology for negatively curved spaces. J. Differential Geom. 67 (2004), no. 3, 395-455.

[57] D. W. Morris, Bounded generation of

S L (n, A)

. New York J. Math. 13 (2007), 383-421.

[58] V. Nekrashevych, Self-similar groups. Math. Surveys Monogr. 117, American Mathematical Society, Providence, RI, 2005.

[59] V. Nekrashevych, Simple groups of dynamical origin. Ergodic Theory Dynam. Systems 39 (2019), no. 3, 707-732.

[60] W. H. Previts and T. S. Wu, Dense orbits and compactness of groups. Bull. Aust. Math. Soc. 68 (2003), no. 1, 155-159.

[61] N. Radu, A classification theorem for boundary 2-transitive automorphism groups of trees. Invent. Math. 209 (2017), no. 1, 1-60.

[62] C. D. Reid, Normal subgroup structure of totally disconnected locally compact groups. In 2016 MATRIX Annals, pp. 525-560, MATRIX Book Ser. 1, Springer, Cham, 2018.

[63] C. D. Reid and P. R. Wesolek, Dense normal subgroups and chief factors in locally compact groups. Proc. Lond. Math. Soc. (3) 116 (2018), no. 4, 760-812.

[64] C. D. Reid and P. R. Wesolek, The essentially chief series of a compactly generated locally compact group. Math. Ann. 370 (2018), no. 1-2, 841-861.

[65] C. D. Reid and P. R. Wesolek, Homomorphisms into totally disconnected, locally compact groups with dense image. Forum Math. 31 (2019), no. 3, 685-701.

[66] M. Rovinsky, Motives and admissible representations of automorphism groups of fields. Math. Z. 249 (2005), no. 1, 163-221.

[67] M. Rubin, Locally moving groups and reconstruction problems. In Ordered groups and infinite permutation groups, pp. 121-157, Math. Appl. 354, Kluwer Acad. Publ., Dordrecht, 1996.

[68] G. Schlichting, Operationen mit periodischen Stabilisatoren. Arch. Math. (Basel) 34 (1980), no. 2, 97-99.

[69] P. Scholze, p-adic geometry. In Proceedings of the International Congress of Mathematicians-Rio de Janeiro 2018. I. Plenary lectures, pp. 899-933, World Sci. Publ., Hackensack, NJ, 2018.

[70] Y. Shalom, Rigidity of commensurators and irreducible lattices. Invent. Math. 141 (2000), no. 1, 1-54.

[71] Y. Shalom and G. A. Willis, Commensurated subgroups of arithmetic groups, totally disconnected groups and adelic rigidity. Geom. Funct. Anal. 23 (2013), no. 5, 1631-1683.

[72] S. M. Smith, A product for permutation groups and topological groups. Duke Math. J. 166 (2017), no. 15, 2965-2999.

[73] T. Tao, Hilbert's fifth problem and related topics. Grad. Stud. Math. 153, American Mathematical Society, Providence, RI, 2014.

[74] O. I. Tavgen, Bounded generability of Chevalley groups over rings of

s

-integer algebraic numbers. Izv. Akad. Nauk SSSR Ser. Mat. 54 (1990), no. 1, 97-122, 221-222.

[75] J. Tits, Algebraic and abstract simple groups. Ann. of Math. (2) 80 (1964), 313-329.

[76] J. Tits, Sur le groupe des automorphismes d'un arbre. In Essays on topology and related topics (MÃ©moires dÃ©diÃ©s Ã Georges de Rham), pp. 188-211, Springer, New York, 1970.

[77] D. Van Dantzig, Zur topologischen Algebra. III. Brouwersche und Cantorsche Gruppen. Compos. Math. 3 (1936), 408-426.

[78] H.-C. Wang, On a maximality property of discrete subgroups with fundamental domain of finite measure. Amer. J. Math. 89 (1967), 124-132.

[79] H.-C. Wang, In Topics on totally discontinuous groups, pp. 459-487, Pure Appl. Math. 8, Dekker, New York, 1972.

[80] J. S. P. Wang, The Mautner phenomenon for

p

-adic Lie groups. Math. Z. 185 (1984), no. 3, 403-412.

[81] A. Weil, L'intÃ©gration dans les groupes topologiques et ses applications. Actual. Sci. Ind. [Curr. Sci. Ind. Top.] 869, Hermann et Cie, Paris, 1940.

[82] P. Wesolek, Elementary totally disconnected locally compact groups. Proc. Lond. Math. Soc. (3) 110 (2015), no. 6, 1387-1434.

[83] P. Wesolek, A survey of elementary totally disconnected locally compact groups. In 2016 MATRIX Annals, pp. 593-611, MATRIX Book Ser. 1, Springer, Cham, 2018.

[84] G. Willis, Totally disconnected groups and proofs of conjectures of Hofmann and Mukherjea. Bull. Aust. Math. Soc. 51 (1995), no. 3, 489-494.

[85] G. A. Willis, The structure of totally disconnected, locally compact groups. Math. Ann. 300 (1994), no. 2, 341-363.

[86] G. A. Willis, Further properties of the scale function on a totally disconnected group. J. Algebra 237 (2001), no. 1, 142-164.

[87] G. A. Willis, Tidy subgroups for commuting automorphisms of totally disconnected groups: an analogue of simultaneous triangularisation of matrices. New York J. Math. 10 (2004), 1-35.

[88] G. A. Willis, Compact open subgroups in simple totally disconnected groups. J. Algebra 312 (2007), no. 1, 405-417.

[89] G. A. Willis, The scale and tidy subgroups for endomorphisms of totally disconnected locally compact groups. Math. Ann. 361 (2015), no. 1-2, 403-442.

[90] T. S. Wu, Continuous automorphisms on locally compact groups. Math. Z. 96 (1967), 256-258.

PIERRE-EMMANUEL CAPRACE

UCLouvain - IRMP, 1348 Louvain-la-Neuve, Belgium,

pierre-emmanuel.caprace@uclouvain.be

GEORGE A. WILLIS

University of Newcastle, Callaghan 2308, Australia, george.willis @ newcastle.edu.au

NEENA GUPTA

ABSTRACT

In this article, we shall discuss the solution to the Zarsiki Cancellation Problem in positive characteristic, various approaches taken so far towards the possible solution in characteristic zero, and several other questions related to this problem.

MATHEMATICS SUBJECT CLASSIFICATION 2020

Primary 14R10; Secondary 14R20,14R25,13B25,13F20,13N15

KEYWORDS

Polynomial ring, cancellation Problem, embedding problem, affine fibration problem, locally nilpotent derivations

1. INTRODUCTION

"Polynomials and power series

May they forever rule the world."

Right from the beginning of the 19th century, mathematicians have been involved in studying polynomial rings (over

C

and over

R

). Some of the early breakthroughs on polynomial rings have led to the foundation of Commutative Algebra. One such result is the Hilbert Basis Theorem, a landmark result on the finite generation of ideals, which solved a central problem on invariant theory. This was followed by the Hilbert Nullstellensatz which connects affine varieties (zero locus of a set of polynomials) with rings of regular functions on varieties and thus enables one to make use of the algebraic machinery of commutative algebra to study geometric properties of varieties.

Affine Algebraic Geometry deals with the study of affine spaces (and certain closed subspaces), equivalently, polynomial rings (and certain quotients). There are many fundamental problems on polynomial rings which can be formulated in an elementary mathematical language but whose solutions remain elusive. Any significant progress requires the development of new and powerful methods and their ingenious applications.

One of the most challenging problems in Affine Algebraic Geometry is the Zariski Cancelation Problem (ZCP) on polynomial rings (Question 1' below). In this article, we shall discuss the solution to the ZCP in positive characteristic, various approaches taken so far towards the possible solution in characteristic zero, and several other questions related to this problem. For a survey on problems in Affine Algebraic Geometry, one may look at

[42, 62, 69]

Throughout the article, all rings will be assumed to be commutative with unity and

k

will denote a field. For a ring

R, R^{*}

will denote the group of units of

R

. We shall use the notation

R^{[n]}

for a polynomial ring in

n

variables over a commutative ring

R

. Thus,

E = R^{[n]}

will mean that

E = R [t_{1}, \dots, t_{n}]

for some elements

t_{1}, \dots, t_{n}

E

which are algebraically independent over

R

. Unless otherwise stated, capital letters like

X_{1}, X_{2}, \dots, X_{n}, Y_{1}, \dots, Y_{m}, X, Y, Z, T

will be used as variables of polynomial rings.

2. CANCELLATION PROBLEM

Let

A

be an affine (finitely generated) algebra over a field

k

. The

k

-algebra

A

is said to be cancellative (over

k

) if, for any

k

-algebra

B, A [X] ≅_{k} B [X]

implies that

A ≅_{k} B

. A natural question in this regard is: which affine domains are cancellative? More precisely:

Question 1. Let

A

be an affine algebra over a field

k

. Suppose that

B

is a

k

-algebra such that the polynomial rings

A [X]

and

B [X]

are isomorphic as

k

-algebras. Does it follow that

A ≅_{k} B

? In other words, is the

k

-algebra

A

cancellative?

A special case of Question 1, famously known as the Zariski Cancellation Problem, asks whether affine spaces are cancellative, i.e., whether any polynomial ring in

n

variables over a field

k

is cancellative. More precisely:

Question 1'. Suppose that

B

is an affine

k

algebra satisfying

B [X] ≅_{k} k [X_{1}, \dots, X_{n + 1}]

for some positive integer

n

. Does it follow that

B ≅_{k} k [X_{1}, \dots, X_{n}]

? In other words, is the polynomial ring

k [X_{1}, \dots, X_{n}]

cancellative?

Abhyankar, Eakin, and Heinzer have shown that any domain

A

of transcendence degree one over any field

k

is cancellative [3]. In fact, they showed that, for any UFD

R

, the polynomial ring

R [X]

is cancellative over

R

. This was further generalized by Hamann to a ring

R

which either contains

Q

or is a seminormal domain [52].

In 1972, Hochster demonstrated the first counterexample to Question 1 [53]. His example, a four-dimensional ring over the field of real numbers

R

, is based on the fact that the projective module defined by the tangent bundle over the real sphere with coordinate ring

S = R [X, Y, Z] / (X^{2} + Y^{2} + Z^{2} - 1)

is stably free but not a free

S

-module.

One of the major breakthroughs in 1970s was the establishment of an affirmative answer to Question 1' for the case

n = 2

. This was proved over a field of characteristic zero by Fujita, Miyanishi, and Sugie [43,70] and over perfect fields of arbitrary characteristic by Russell [74]. Later, it has been shown that even the hypothesis of perfect field can be dropped [20]. A simplified proof of the cancellation property of

k [X, Y]

for an algebraically closed field

k

is given by Crachiola and Makar-Limanov in [22].

Around 1989, Danielewski [26] constructed explicit two-dimensional affine domains over the field of complex numbers

C

which are not cancellative over

C

. New examples of noncancellative varieties over any field

k

have been studied in

[9, 32, 49]

. This addresses the Cancellation Problem, as formulated in Question 1, for all dimensions.

In [45] and [47], the author settled the Zariski Cancellation Problem (Question 1') completely for affine spaces in positive characteristic. She has first shown in [45] that a certain threefold constructed by Asanuma is a counterexample to the ZCP in positive characteristic for the affine three space. Later in [46], she studied a general threefold of the form

x^{m} y = F (x, z, t)

, which includes the Asanuma threefold as well as the famous Russell cubic defined below. A major theorem of [46] is stated as Theorem 5.4 of this article. In [47], using a modification of the theory developed in [46], she constructed a family of examples which are counterexamples to the ZCP in positive characteristic in all dimensions greater than 2 . The ZCP is still a challenging problem in characteristic zero. A few candidate counterexamples are discussed below.

The Russell cubic. Let

A = C [X, Y, Z, T] / (X^{2} Y + X + Z^{2} + T^{3}), V = Spec A

and let

x

denote the image of

X

A

. The ring

A

, known as the Russell cubic, is one of the simplest examples of the Koras-Russell threefolds, a family of threefolds which arose in the context of the problem of determining whether there exist nonlinearizable

C^{*}

-actions on

C^{3}

. It was an exciting open problem for some time whether

A ≅ C^{[3]}

. It was first observed that the ring

A

(respectively the variety

V

) has several properties in common with

C^{[3]}

(respectively

C^{3}

), for instance,

(i)

A

is a regular UFD.

(ii) There exists an injective

C

-algebra homomorphism from

A

C^{[3]}

. Note that

C^{[3]} ↪ A

(iii) The variety

V

is homeomorphic (in fact, diffeomorphic) to

R^{6}

(iv)

V

has logarithmic Kodaira dimension

- \infty

These properties appeared to provide evidence in favor of the surmise that

A ≅ C^{[3]}

. The establishment of an isomorphism between

A

and

C^{[3]}

would have led to counterexamples to the "Linearization Conjecture" on

C^{3}

(stated in [58]) and the Abhyankar-Sathaye Conjecture for

n = 3

(stated in Section 5 of the present article). Indeed, if

A

were isomorphic to

C^{[3]}

, as was then suspected, it would have shown the existence of nonlinearizable

C^{*}

-actions on

C^{3}

. Moreover, note that

(v)

A / (x - λ) = C^{[2]}

for every

λ \in C^{*}

(vi)

A / (x) \neq C^{[2]}

Therefore, if

A

were isomorphic to

C^{[3]}

, then property (vi) would show that

x - λ

cannot be a coordinate in

A

for any

λ

and then, by property (v), it would have yielded a counterexample to the Abhyankar-Sathaye Conjecture for

n = 3

However, Makar-Limanov proved [65] that

A \neq C^{[3]}

; for this result, he introduced a new invariant which distinguished between

A

and

C^{[3]}

. This invariant, which he had named AK-invariant, is now named Makar-Limanov invariant and is denoted by ML. It is defined in Section 3. Makar-Limanov proved that

(vii)

ML (A) = C [x]

(Makar-Limanov [65]).

However, the Makar-Limanov invariant of

C^{[n]}

C

for any integer

n \geq 1

. Thus

A ⊈ C^{[3]}

. Subsequently, other Koras-Russell threefolds were shown to be not isomorphic to the polynomial ring. Eventually, Kaliman-Koras-Makar-Limanov-Russell proved that every

C^{*}

-action on

C^{3}

is linearizable (cf. [55]).

Now for ZCP in characteristic zero, a crucial question, still open, is whether

A^{[1]} = C^{[4]}

. Because if

A^{[1]} = C^{[4]}

, then

A

would be a counterexample to the ZCP in characteristic zero for

n = 3

. In this context, the following results have been proved:

(viii)

ML (A^{[1]}) = C

(Dubouloz [30]).

(ix)

V

A^{1}

-contractible (Dubouloz-Fasel [31], also see [33,54]).

Note that

A^{[1]} = C^{[4]}

would imply that

ML (A^{[1]}) = C

and Dubouloz's result (viii) shows that the latter indeed holds. On the other hand, Asok had suggested a program for showing that the variety

V

is not

A^{1}

-contractible and hence

A

is not a stably polynomial
ring (see [54]). However, Hoyois, Krishna, and Ã˜stvÃ¦r have proved [54] that a step in his program does not hold for

V

. They had further shown that

V

is stably

A^{1}

-contractible. In a remarkable paper [31], Dubouloz and Fasel have established that

V

is in fact

A^{1}

-contractible, which seems to provide further evidence in favor of

A^{[1]} = C^{[4]}

. The variety

V

is in fact the first example of an

A^{1}

-contractible threefold which is not algebraically isomorphic to

C^{3}

Nonrectifiable epimorphisms and Asanuma's rings. Let

m \leq n

be two integers. A

k

-algebra epimorphism

ϕ : k [X_{1}, \dots, X_{n}] \to k [Y_{1}, \dots, Y_{m}]

is said to be rectifiable if there exists a

k

-algebra automorphism

ψ

k [X_{1}, \dots, X_{n}]

such that

ϕ_{\circ} ψ (X_{i}) = Y_{i}

for

1 \leq i \leq m

and

ϕ_{\circ} ψ (X_{j}) = 0

for

m + 1 \leq j \leq n

. Equivalently, over an algebraically closed field

k

, a

k

embedding

Φ : A_{k}^{m} ↪ A_{k}^{n}

is said to be rectifiable if there exists an automorphism

Ψ

A_{k}^{n}

such that

Ψ_{\circ} Φ

is the canonical embedding mapping

(y_{1}, \dots, y_{m}) \to (y_{1}, \dots, y_{m}, 0, \dots, 0)

A famous theorem of Abhyankar-Moh and Suzuki proves that any epimorphism

ϕ : k [X, Y] \to k [T]

is rectifiable in characteristic zero [5,86]. On the other hand, in positive characteristic, there exist nonrectifiable epimorphisms from

k [X, Y]

k [T]

(see Segre [83], Nagata [71]). It is an open problem whether there exist nonrectifiable epimorphisms over the field of complex numbers (see [38]).

Asanuma has described an explicit method for constructing affine rings which are stably polynomial rings, by making use of nonrectifiable epimorphisms ([7], also see [38, PROPOSITION 3.7]). Such rings are considered to be potential candidates for counterexamples to the ZCP. For instance, when

k

is of positive characteristic, nonrectifiable epimorphisms from

k [X, Y]

k [T]

yield counterexamples to the ZCP.

Let

ϕ : R [X, Y, Z] \to R [T]

be defined by

ϕ (X) = T^{3} - 3 T, ϕ (Y) = T^{4} - 4 T^{2}, ϕ (Z) = T^{5} - 10 T

Shastri constructed the above epimorphism

ϕ

and proved that it defines a nonrectifiable (polynomial) embedding of the trefoil knot in

A_{R}^{3}

[84]. Using a result of Serre [63, tHEoREM 1, P. 281], one knows that

\ker (ϕ) = (f, g)

for some

f, g \in k [X, Y, Z]

. Using

f

and

g

, Asanuma constructed the ring

B = R [T] [X, Y, Z, U, V] / (T^{d} U - f, T^{d} V - g)

and proved that

B^{[1]} = R [T]^{[4]} = R^{[5]} (c f

. [7, cORoLLARY 4.2]). He asked [7, REMARK 7.8]:

Question 2. Is

B = R^{[4]}

The interesting aspect of the question is that once the problem gets solved, irrespective of whether the answer is "Yes" or "No," that is, either way, one would have solved a major problem in Affine Algebraic Geometry. Indeed:

B = R^{[4]}

, then there exist nonlinearizable

R^{*}

-actions on the affine four-space

A_{R}^{4}

B \neq R^{[4]}

, then clearly

B

is a counterexample to the ZCP!!

3. CHARACTERIZATION PROBLEM

The Characterization Problem in affine algebraic geometry seeks a "useful characterization" of the polynomial ring or, equivalently (when the ground field is algebraically
closed), an affine

n

-space. For instance, the following two results give respectively an algebraic and a topological characterization of

k^{[1]}

(or

A_{C}^{1}

Theorem 3.1. Let

k

be an algebraically closed field of characteristic zero. Then the polynomial ring

k^{[1]}

is the only one-dimensional affine UFD with

A^{*} = k^{*}

Theorem 3.2. Let

k

be the field of complex numbers

C

. Then the affine line

A_{C}^{1}

is the only acyclic normal curve.

While the Characterization Problem is one of the most important problems in affine algebraic geometry in its own right, it is also closely related to some of the challenging open problems on the affine space like the "Cancellation Problem." For instance, each of the above characterizations of

k^{[1]}

immediately solves the Cancellation Problem in dimension one:

A^{[1]} = k^{[2]} ⟹ A = k^{[1]}

. The complexity of the Characterization Problem increases with the dimension of the rings.

In his attempt to solve the Cancellation Problem for the affine plane, Ramanujam obtained a remarkable topological characterization of the affine plane

C^{2}

in 1971 [72]. He proved that

Theorem 3.3.

C^{2}

is the only contractible smooth surface which is simply connected at infinity.

Ramanujam also constructed contractible surfaces which are not isomorphic to

C^{2}

. Soon, in 1975, Miyanishi [67] obtained an algebraic characterization of the polynomial ring

k^{[2]}

. He proved that

Theorem 3.4. Let

k

be an algebraically closed field of characteristic zero and

A

be a twodimensional affine factorial domain over

k

. Then

A = k^{[2]}

if and only if it satisfies the following:

(i)

A^{*} = k^{*}

(ii) There exists an element

f \in A

and a subring

B

A

such that

A [f^{- 1}] =

B {[f^{- 1}]}^{[1]}

This algebraic characterization was used by Fujita, Miyanishi, and Sugie [43,70] to solve the Cancellation Problem for

k [X, Y]

. In 2002 [50], using methods of Mumford and Ramanujam, Gurjar gave a topological proof of the cancellation property of

C [X, Y]

Remarkable characterizations of the affine three space were obtained by Miyanishi [68] and Kaliman [56] (also see [69] for a beautiful survey). We state below the version of Kaliman.

Theorem 3.5. Let A be a three-dimensional smooth factorial affine domain over the field of complex numbers

C

. Let

X = Spec A

. Then

A = C^{[3]}

if and only if it satisfies the following:

(i)

A^{*} = C^{*}

(ii)

H_{3} (X, Z) = 0

, or

X

is contractible.
(iii)

X

contains a cylinder-like open set

V

such that

V ≅ U \times A^{2}

for some curve

U

and each irreducible component of the complement

X ∖ V

has at most isolated singularities.

When

A^{[1]} = C^{[4]}

, it is easy to see that

A

possesses properties (i) and (ii) of Theorem 3.5. Thus, by Theorem 3.5 , the ZCP for

C^{[3]}

reduces to examining whether condition (iii) necessarily holds for a

C

-algebra

A

satisfying

A^{[1]} = C^{[4]}

In [29], we have obtained another characterization of the affine three-space using certain invariants of an affine domain defined by locally nilpotent derivations. We state it below.

Locally nilpotent derivations and a characterization of

C^{[3]}

. Let

B

be an affine domain over a field

k

of characteristic zero. A

k

-linear derivation

D

B

is said to be a locally nilpotent derivation if, for any

a \in B

there exists an integer

n

(depending on

a

) satisfying

D^{n} (a) = 0

. Let

LND (B)

denote the set of all locally nilpotent

k

-derivations of

B

and let

{LND}^{*} (B) = {D \in LND (B) ∣ D s = 1 for some s \in B}

Then we define

ML (B) := ⋂_{D \in LND (B)} \ker D and {ML}^{*} (B) := ⋂_{D \in {LND}^{*} (B)} \ker D

The above

ML (B)

, introduced by Makar-Limanov, is now called the Makar-Limanov invariant of

B

; ML*

^{*} (B)

was introduced by Freudenburg in [41, P. 237]. We call it the MakarLimanov-Freudenburg invariant or ML-F invariant. If

{LND}^{*} (B) = \emptyset

, we define

{M L}^{*} (B)

to be

B

. We have obtained the following theorem [29, THEOREM 4.6].

Theorem 3.6. Let A be a three-dimensional affine factorial domain over an algebraically closed field

k

of characteristic zero. Then the following are equivalent:

(I)

A = k^{[3]}

(II)

{ML}^{*} (A) = k

(III)

ML (A) = k

and

{ML}^{*} (A) \neq A

A similar result has also been proved in dimension two under weaker hypotheses [29, theorem 3.8]. The above characterization of the affine three-space does not extend to higher dimensions [29, EXAMPLE 5.6]. So far, no suitable characterization of the affine

n

-space for

n \geq 4

is known to the author.

4. AFFINE FIBRATIONS

Let

R

be a commutative ring. A fundamental theorem of Bass-Connell-Wright and Suslin

[10, 85]

on the structure of locally polynomial algebras states that:

Theorem 4.1. Let

A

be a finitely presented algebra over a ring R. Suppose that for each maximal ideal

m

R, A_{m} = R_{m}^{[n]}

for some integer

n \geq 0

. Then

A ≅ {Sym}_{R} (P)

for some finitely generated projective

R

-module

P

of rank

n

Now for a prime ideal

P

R

, let

k (P)

denote the residue field

R_{P} / P R_{P}

. The area of affine fibrations seeks to derive information about the structure and properties of an

R

-algebra

A

from the information about the fiber rings

A \otimes_{R} k (P) (= A_{P} / P A_{P})

A

at the points

P

of the prime spectrum of

R

, i.e., at the prime ideals

P

R

R

-algebra

A

is said to be an

A^{n}

-fibration over

R

A

is a finitely generated flat

R

-algebra and for each prime ideal

P

R, A \otimes_{R} k (P) = k (P)^{[n]}

The most important problem on

A^{n}

-fibrations, due to VeÇsfeÇler and DolgaÄev [87], can be formulated as follows:

Question 3. Let

R

be a Noetherian domain of dimension

d

and

A

be an

A^{n}

-fibration over

R

(i) If

R

is regular, is

A ≅ {Sym}_{R} (Q)

for some projective module

Q

over

R

? (In particular, if

R

is regular local, is then

A = R^{[n]}

(ii) In general, what can one say about the structure of

A

Question 3 is considered a hard problem. When

n = 1

, it has an affirmative answer for all

d

. This has been established in the works of Kambayashi, Miyanishi, and Wright [59,60]. Their results were further refined by Dutta who showed that it is enough to assume the fiber conditions only on generic and codimension-one fibers ([34]; also see [14, 17, 40]).

In case

n = 2, d = 1

, and

R

contains the field of rational numbers, an important theorem of Sathaye [81] gives an affirmative answer to Question 3 (i). To prove this theorem, Sathaye first generalized the Abhyankar-Moh expansion techniques originally developed over

k [[x]]

k [[x_{1}, \dots, x_{n}]]

[80]. The expansion techniques were used by Abhyankar-Moh to prove their famous epimorphism theorem. The generalized expansion techniques were further developed by Sathaye [82] to prove a conjecture of Daigle and Freudenburg. The result was a crucial step in Daigle-Freudenburg's theorem that the kernel of any triangular derivation of

k [X_{1}, X_{2}, X_{3}, X_{4}]

is a finitely generated

k

-algebra [23].

When the residue field of

R

is of positive characteristic, Asanuma has shown in [6, THEOREM 5.1] that Question 3 (i) has a negative answer for

n = 2, d = 1

, and the author has generalized Asanuma's ring [47] to give a negative answer to Question 3 (i) for

n = 2

and any

d > 1

(also see [48]). In Theorem 5.4, the author proved that in a special situation

A^{2}

-fibration is indeed trivial.

However, if

n = 2, d = 2

, and

R

contains the field of rational numbers, Question 3 (i) is an open problem. A candidate counterexample is discussed in Section 7.

In the context of Question 3 (ii), a deep work of Asanuma [6] provides a stable structure theorem for

A

. As a consequence of Asanuma's structure theorem, it follows that if

R

is regular local, then there exists an integer

m \geq 0

such that

A^{[m]} = R^{[m + n]}

. Thus it is very tempting to look for possible counterexamples to the affine fibration problem in order to
obtain possible counterexamples to the ZCP in characteristic zero. One can see

[12, 24, 36, 37]

and [38, SECTION 3.1] for more results on affine fibrations.

So far we have considered affine fibrations where the fibre rings are polynomial rings. Bhatwadekar and Dutta have obtained some nice results on rings whose fiber rings are of the form

k [X, 1 / X] [15, 16]

. Later Bhatwadekar, the author, and A. Abhyankar studied rings whose fiber rings are Laurent polynomial algebras or rings of the form

k [X, 1 / f (X)]

, or of the form

k [X, Y, 1 / (a X + b), 1 / (c Y + d)]

for some

a, b, c, d \in k [1, 2, 18, 19, 44]

. One of the results of Bhatwadekar and the author provides a Laurent polynomial analogue of Theorem 4.1 and the affine fibration problem Question 3. More generally, we have [19, THEOREMS A AND C]:

Theorem 4.2. Let

R

be a Noetherian normal domain with field of fractions

K

and

A

be a faithfully flat

R

4.3. Iterations of generalized P H P H PH\mathbf{P H}PH and correctness statements

5. INDICATORS AND CORRECTNESS STATEMENTS

5.1. Models of first- and second-order arithmetic

5.2. Indicators

5.3. Indicators corresponding to largeness notions

ACKNOWLEDGMENTS

FUNDING

REFERENCES

KEITA YOKOYAMA

CONSTRAINT SATISFACTION PROBLEM: WHAT MAKES THE PROBLEM EASY

DMITRIY ZHUK

Abstract

MATHEMATICS SUBJECT CLASSIFICATION 2020

KEYWORDS

1. INTRODUCTION

2. CONSTRAINT SATISFACTION PROBLEM

2.1. Examples

2.2. Reduction from one language to another

2.3. Polymorphisms as invariants

2.4. Local consistency

2.5. CSP over a 2-element domain

2.6. CSP solvable by local consistency checking

2.7. CSP Dichotomy Conjecture

2.8. How to solve CSP if pp-definable relations are simple

2.9. System of linear equations in Z 2 Z 2 Z_(2)\mathbb{Z}_{2}Z2

2.10. 2-satisfability

2.11. Strong subuniverses and a proof of the CSP Dichotomy Conjecture

Theorem 2.9 ([47]). Suppose

2.12. Conclusions

3. QUANTIFIED CSP

3.1. PGP reduction for Π 2 Î 2 Pi_(2)\Pi_{2}Î 2 restrictions

3.2. A general PGP reduction

3.3. Does EGP mean hard?

3.4. Surprising constraint language and the QCSP on a 3-element domain

3.5. Conclusions

4. OTHER VARIANTS OF CSP

4.1. CSP over an infinite domain

4.2. Surjective Constraint Satisfaction Problem

4.3. Promise CSP

REFERENCES

DMITRIY ZHUK

A TOTALLY DISCONNECTED INVITATION TO LOCALLY COMPACT GROUPS

ABSTRACT

MATHEMATICS SUBJECT CLASSIFICATION 2020

KEYWORDS

1. INTRODUCTION

2. DECOMPOSITION THEORY

2.1. Normal subgroup structure

2.2. Elementary groups

2.3. More on chief factors

3. SIMPLE GROUPS

3.1. Dense embeddings and local structure

3.2. Applications to lattices

3.3. Applications to commensurated subgroups

4. SCALE METHODS

4.1. Contraction and other groups

4.2. Flat groups of automorphisms

5. FUTURE DIRECTIONS

ACKNOWLEDGMENTS

FUNDING

REFERENCES

PIERRE-EMMANUEL CAPRACE

GEORGE A. WILLIS

THE ZARISKI CANCELLATION PROBLEM AND RELATED PROBLEMS IN AFFINE ALGEBRAIC GEOMETRY

NEENA GUPTA

ABSTRACT

MATHEMATICS SUBJECT CLASSIFICATION 2020

KEYWORDS

1. INTRODUCTION

2. CANCELLATION PROBLEM

3. CHARACTERIZATION PROBLEM

4. AFFINE FIBRATIONS

4.3. Iterations of generalized $P H$ and correctness statements

2.9. System of linear equations in $Z_{2}$

3.1. PGP reduction for $Π_{2}$ restrictions

THE ZARISKI
CANCELLATION PROBLEM AND RELATED PROBLEMS IN AFFINE ALGEBRAIC GEOMETRY